Комбинаторика. Из истории комбинаторики

Из истории комбинаторики
С комбинаторными задачами люди столкнулись в глубокой древности. В Древнем Китае увлекались составлением магических квадратов. В Древней Греции занимались теорией фигурных чисел.
Комбинаторные задачи возникли и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т.д. Комбинаторика становится наукой лишь в 18 в. – в период, когда возникла теория вероятности.

Комбинаторика – это раздел математики, в котором изучаются различные соединения (комбинации) элементов конечных множеств.
Выбором объектов и расположением их в том или ином порядке приходится заниматься чуть ли не во всех областях человеческой деятельности, например конструктору, разрабатывающему новую модель механизма, ученому-агроному, планирующему распределение с/х культур на нескольких полях, химику, изучающему строение органических молекул, имеющих данный атомный состав.

Элементарные комбинаторные конфигурации:
сочетания,
размещения,
перестановки.
Для подсчета числа этих конфигураций используются правила суммы и произведения

Если некоторый объект a можно выбрать n1 способами, а объект в можно выбрать n2 способами, причем первые и вторые способы не пересекаются, то любой из объектов (a или в) можно выбрать n1 + n2 способами.
Правило сложения

Пример1. Имеется 8 шаров: в 1 ящик положили 5 шт., а во 2 ящик - 3 шт. Сколькими способами можно вытащить 1 шар?
Решение:
из 1 ящика шар можно вытащить 5-ю способами, а из второго 3-мя. Значит, всего 5+3=8 способов

Правило умножения

Пример 2. На входной двери дома установлен домофон, на котором нанесены цифры 0,1,2,…9.Каждая квартира получает кодовый замок из двух цифр типа 0-2, 3-7 и т.п. Хватит ли кодовых замков для всех квартир, если в доме 96 квартир? (код 0-0 не существует)
Решение:
Выбор 1-й цифры – 10 вариантов, 2-й –10 вариантов.
Всего 10х10 – 1 = 99 вариантов
Ответ: хватит.

Правило включения-исключения
Пусть у множества А и В общая часть насчитывает k элементов Тогда в объединении множеств А и В число элементов равно m+n-k, т. е.
m
n
k

Пример3. В группе каждый студент занимается в спортивной секции. При этом 20 студентов занимаются волейболом, 12 – баскетболом, а 7 студентов посещают обе секции. Сколько студентов в группе?
Решение:
если сложить количество студентов, посещающих обе секции, мы учтем всех студентов и тех которые посещают обе секции, применив правило включения-исключения получим 20+12-7=25.
Ответ: в группе 25 студентов

Размещения

Обозначение:
⎯ читают «А из эн по k»

Сколько различных двузначных чисел можно записать с помощью цифр 1, 2, 3, 4 при условии, что в каждой записи нет одинаковых цифр?
12, 13, 14,
21, 23, 24,
31, 32, 34,
41, 42, 43.
2 способ – по правилу произведения: m = 4, n = 3; mn = 12
Ответ: 12
Из задачи видно, что любые два соединения отличаются либо составом элементов (12 и 24), либо порядком их расположения (12 и 21). Такие соединения называют размещениями.
Задача 1
1 способ – перебором вариантов:

Сколькими способами можно обозначить данный вектор, используя буквы A, B, C, D?
Решение:
Действительно, это наборы (AB),(BA),(AC),(CA),(AD),(DA),(BC),(CB),(BD),(DB),(CD),(DC).

Перестановки

Перестановками из n элементов называются соединения (комбинации), которые состоят из одних и тех же n элементов и отличаются одно от другого только порядком их расположения.
Задача 1:
Сколькими способами можно поставить рядом на полке 4 различные книги?

Задача 2. Даны цифр: 1,2,3,4,5,6,7. Сколько различных семизначных чисел можно составить из этих цифр? Каждое число является перестановкой из 7 элементов.
Примеры: 1234567, 2354167, 7546321.
Перестановка-упорядоченное множество.
Число перестановок из n элементов вычисляют по формуле .
По условию n=7
Так из 7 цифр можно
различных чисел.

Сочетания

Решение
Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:
.
Пример 1. Необходимо выбрать в подарок 4 из имеющихся 1- различных книг. Сколькими способами это можно сделать?

Различие между перестановками, размещениями, сочетаниями
В случае перестановок берутся все элементы и изменяется только их местоположение.
В случае размещений берётся только часть элементов и важно расположение элементов друг относительно друга.
В случае сочетаний берётся только часть элементов и не имеет значения расположение элементов друг относительно друга.

Схема выбора
с возвращением

Перестановки с повторениями.
Пусть в множестве из n элементов есть k различных типов элементов, при этом 1-й тип элементов повторяется n1 раз, 2-й – n2 раз, …k-й - nk раз, причем n1 + n2 + …. + nk = n. Тогда перестановки элементов данного множества представляют собой перестановки с повторениями. Число перестановок с повторениями (иногда говорят о числе разбиений множества) из n элементов обозначается символом Pn (n1,n2, …. , nk) и вычисляется по формуле:
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Решение
Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

Размещения с повторениями.
Если при упорядоченной выборке k элементов из n элементов возвращаются обратно, то полученные выборки представляют собой размещения с повторениями. Число всех размещений с повторениями из n элементов по k обозначаются символом и вычисляются по формуле
А = n
k
n
k
А
n
k

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Решение
Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.
n
k
k
n+k-1