Курс по комбинаторике
Начал на днях проходить массовый открытый онлайн курс (MOOC) на курсере по комбинаторике. В этом посте буду отмечать основные моменты, которые я узнал в нем.
Основные правила комбинаторики
Правило сложения
Пусть дано множество $A\left\{a_1,...,a_n\right\}$ и множество $B\left\{b_1,...,b_m\right\}$, тогда количество способов, которыми можно отобрать объект либо из первого множества, либо из второго равно $n+m$.
Правило умножения
Пусть дано множество $A\left\{a_1,...,a_n\right\}$ и множество $B\left\{b_1,...,b_m\right\}$, тогда количество способов, которыми можно сначала извлечь объект из А, а затем вслед за ним извлечь произвольный объект из B равно $n\cdot m$.
Сколько существует шестизначных чисел? На первое место можно поставить одну из девяти цифр $\left\{1,2,3,4,5,6,7,8,9\right\}$, на оставшиеся места можно поставить любую из цифр $\left\{0,1,2,3,4,5,6,7,8,9\right\}$, по правилу умножения получаем $9\cdot 10^5$.
Принцип Дирихле
Пусть есть $n+1$ объектов и $n$ мест для их размещения, тогда найдется хотя бы одно место, в котором будет размещено хотя бы $2$ объекта.
Задача про первокурсников в кинотеатре
Пусть есть $20$ первокурсников и $1$ семинарист, надо посчитать количество рассадок в одном ряду, в котором $21$ место, причем семинарист должен сидеть с краю, а Петя, Коля и Вася не должны сидеть вместе.
Семинарист должен сидеть по краям, поэтому есть $2$ варианта рассадки семинариста, общее количество рассадок первокурсников будет равно $20!$, потому что на первую позицию можно посадить $20$ студентов, на вторую $19$ и так далее, по правилу умножения получаем $20!$. Те ситуации, когда Петя, Коля и Вася сидят вместе можно посчитать, считая Петю, Колю и Васю за одного человека, тогда получается, что надо умножить количество рассадок $18$ человек ($18!$) на количество рассадок Пети, Коли и Васи, когда они вместе ($3!$). Таким образом ответ:
$$2\cdot(20! - 18!\cdot3!)$$
Сочетания и Размещения
Пусть дано множество $A\left\{a_1,...,a_n\right\}$, если мы отбираем из него элементы с учетом места каждого элемента, то это - размещение, а если без учета мест - сочетание. Например, есть множество букв $\left\{а,...,я\right\}$, тогда слово "лягушка" - это размещение, слово "гуляшка" - другое размещение. Но сочетание $\left\{л,я,г,у,ш,к,а\right\}$ это то же самое сочетание что и $\left\{г,у,л,я,ш,к,а\right\}$, потому что в сочетании не важно расположение элементов.
Также могут быть сочетания с повторениями и без, так и размещения с повторениями и без. Например, слово "жаба" - это размещение с повторениями, а множество $\left\{ж,а,б,а\right\}$ - это сочетание с повторениями.
$\bar{A_n^k}$ - число $k$ - размещений с повторениями
$A_n^k$ - число $k$ - размещений без повторений
$C_n^k$ - число $k$ - сочетаний без повторений
$\bar{С}_n^k$ - число $k$ - сочетаний с повторениями
Теорема 1. $$\bar{A_n^k}=n^k$$
На первую позицию можно поставить $n$ объектов, на вторую тоже $n$ и т.д., получаем $n\cdot n\cdot ...\cdot n=n^k$
Теорема 2. $$A_n^k=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot(n-k+1)=\frac{n!}{(n-k)!}$$
На первую позицию можно поставить $n$ объектов, на вторую $n-1$ и т.д., на $k-ю$ $n-k+1$
Если взять $A_n^n$, то получится $A_n^n=n!$ - это количество перестановок
Теорема 3. $$С_n^k=\frac{A_n^k}{k!}=\frac{n!}{k!(n-k)!}$$
$k$ - сочетанию без повторений соответствует $k!$ его перестановок, являющихся $k$ - размещениями. Сочетаний без повторений в $k!$ раз меньше, чем размещений без повторений.
Теорема 4. $$\bar{С}_n^k=C_{n+k-1}^k$$
Построим биекцию между $k$-сочетаниями с повторением из множества $\left\{a_1,...,a_n\right\}$ и последовательностями из $0$ и $1$ специального вида.
Рассмотрим произвольное $k$-сочетание с повторениями. Посчитаем, сколько раз в этом $k$-сочетании встречается $a_1$ (это может случиться от $0$ до $k$ раз), и рисуем такое количество $1$. Если не встречается, то ничего не пишем.
После этого пишем $0$, и пишем столько $1$, сколько раз в $k$-сочетании встречается $a_2$, и т.д. В последнюю очередь пишем столько единиц, сколько раз встречается $a_n$.
В итоге мы получаем последовательность длины $n+k−1$ из $0$ и $1$, в которой ровно $n−1$ нулей и ровно $k$ единиц.
Легко показать, что по любой такой последовательности можно восстановить $k$-сочетание. Таким образом, мы получаем биекцию между $k$-сочетаниями с повторениями и такими последовательностями из $0$ и $1$. Их количество равно способу выбрать $k$ единиц на $n+k−1$ позиции, то есть $C_{n+k−1}^k$.
Задача про случайный выбор элементов
Пусть у нас есть 10 разных элементов, и мы 3 раза выбраем 2 случайных элемента. Какова вероятность, что все 3 раза мы отбирем уникальные элементы? Тоесть какова вероятность, что выбранные элементы не повторятся?
Сначала давайте попробуем смоделировать ситуацию на питоне:
1 # -*- coding: utf-8 -*- 2 import random 3 4 5 def get_samples(n, m, k): 6 """ n - кол-во элементов 7 m - сколько отбираем за раз 8 k - число выборок 9 """ 10 samples = [] 11 # исходный массив 12 alist = range(1, n+1) 13 # k раз делаем выборки: 14 for _ in range(k): 15 sample = random.sample(alist, m) 16 samples.extend(sample) 17 # делаю сет из листа (в сете остаются только уникальные элементы) 18 set_sam = set(samples) 19 if len(samples) == len(set_sam): 20 return 'unique' 21 else: 22 return 'not_unique' 23 24 25 results = dict(unique=0, not_unique=0) 26 N = 100000 27 for _ in range(N): 28 results[get_samples(10, 2, 3)] += 1 29 30 print(float(results['unique'])/N)
Данный код дает вероятность уникальных элементов в районе 20%. Теперь применим формулу комбинаторики, и посмотрим, получится ли такой же результат. Ясно, что при первой выборке вероятность уникальных элементов 100%. При второй выборке количество уникальных исходов уменьшится на $9+8$ - то есть на количество тех вариантов, в которых задействованы элементы, выбранные при первой выборке, при третьей выборке количество уникальных выборок уменьшится на $9+8+7+6$. Общее количество сочетаний при каждой выборке - это $C_{10}^2$. Получаем искомую вероятность уникальных элементов во всех 3 случаях:
$$1\cdot \frac{C_{10}^2-(9+8)}{C_{10}^2}\cdot \frac{C_{10}^2-(9+8+7+6)}{C_{10}^2}=\frac{28}{45}\cdot \frac{15}{45}=0.207$$
Теория сошлась с экспериментом!
Задача про носки
В ящике лежат семь белых, пять красных и три черных носка. Носки считаются парой, если они имеют один цвет. Наугад из ящика выбирается четыре произвольных носка. Найдите вероятность того, что среди выбранных встретятся две пары разных цветов.
Сначала давайте попробуем смоделировать ситуацию на питоне:
1 import random 2 3 4 def get_samples(): 5 alist = ['w']*7 + ['r']*5 + ['b']*3 6 random.shuffle(alist) 7 samples = random.sample(alist, 4) 8 set_samples = list(set(samples)) 9 if (samples.count(set_samples[0]) == 2 and 10 samples.count(set_samples[1]) == 2): 11 return 'two_pairs' 12 else: 13 return 'no' 14 15 16 results = dict(two_pairs=0, no=0) 17 N = 1000000 18 for _ in range(N): 19 results[get_samples()] += 1 20 21 print(float(results['two_pairs'])/N)
Этот код дает вероятность того, что среди выбранных 4 носков будут 2 пары примерно 0.22. Давайте проверим это, найдя аналитическое решение.
Всего возможных исходов будет $C_{15}^4$, потому что мы отбираем 4 носка, а всего их 15. Это пойдет в знаменатель, теперь нужно подсчитать количество вариантов выбрать 2 белых 2 красных, 2 белых 2 черных, 2 красных 2 черных. То есть:
$$P=\frac{C_{7}^{2}\cdot C_{5}^{2}+C_{7}^{2}\cdot C_{3}^{2}+C_{5}^{2}\cdot C_{3}^{2}}{C_{15}^{4}}=0.2219$$
Теория снова сошлась с экспериментом, это прекрасно!
Бином Ньютона
$$(x+y)^n=\sum_{k=0}^nC^k_nx^ky^{n-k}$$
Числа сочетаний также выступают в роли биномиальных коэффициентов.
Вопрос. Есть $n_1$ символов $a_1$, $n_2$ символов $a_2$, …, $n_k$ символов $a_k$. Пусть $n=n_1+…+n_k$ − общее количество символов. Сколько можно составить различных слов длины $n$ из такого набора символов?
Теорема. Обозначим через $P(n_1,…,n_k)$ искомое количество слов длины $n$. Тогда $P(n_1,\ldots,n_k) = \frac{n!}{n_1!\cdot n_2! \ldots n_k!}$.
Полиномиальная формула
Мы хотим найти полиномиальную формулу, то есть формулу для нахождения $(x_1+\ldots+x_k)^n$. Ясно, что полиномиальная формула является обобщением биномиальной.
$$(x_1+\ldots+x_k)^n = \sum_{(n_1,\ldots,n_k): \forall i \; n_i \in \{0,1,\ldots,n\}, n_1+\ldots+n_k=n}P(n_1,\ldots,n_k) \cdot x_1^{n_1} \cdot x_2^{n_2} \cdot \ldots \cdot x_k^{n_k}$$
Формула включений и исключений
Пусть $\alpha_1,\ldots,\alpha_N$ − объекты, объекты, $\alpha_1,\ldots,\alpha_n$ − свойства, присущие указанным объектам.
Пример: $\alpha_1,\ldots,\alpha_N$ − люди в аудитории, свойства − любые, например, свойство "хорошо знать комбинаторику" или "знание иностранных языков" или более экзотические.
Выделим следующие свойства: $\alpha_1$ − "знание английского языка", $\alpha_2$ − "знание французского языка", $\alpha_3$ − "знание немецкого языка". Обозначим через $N(\alpha_1)$ количество объектов среди исходных, которые обладают свойством $\alpha_1$, через $N(\alpha_2)$ − количество объектов среди исходных, которые обладают свойством $\alpha_2$, и так далее, через $N(\alpha_n)$ − количество объектов среди исходных, которые обладают свойством $\alpha_n$.
По аналогии, через $N(\alpha_1,\alpha_2)$ обозначим количество объектов, которые обладают свойством $\alpha_1$ и свойством $\alpha_2$, …, через $N(\alpha_{n−1},\alpha_n)$ обозначим количество объектов, которые обладают свойством $\alpha_{n−1}$ и свойством $\alpha_n$. Всего таких пар свойств будет ровно $C^2_n$.
Аналогично определяем количества $N(\alpha_{n-2},\alpha_{n-1},\alpha_n)$, $\ldots$. Последним будет определено $N(\alpha_1,\alpha_2, \ldots,\alpha_n)$ − количество объектов, которые обладают всеми свойствами $\alpha_1, \alpha_2,\ldots,\alpha_n$.
Кроме того, через $\alpha_i'$ обозначим отрицание к свойству $\alpha_i$, то есть этим свойством обладают объекты, для которых не выполнено свойство $\alpha_i$. Наша цель − найти количество людей, для которых не выполнено ни одно из свойств $\alpha_1,\alpha_2,\ldots,\alpha_n$. Пример: в случае трёх множеств получаем формулу:
$$N(\alpha_1',\ldots,\alpha_3') = N - N(\alpha_1) - N(\alpha_2) - N(\alpha_3) + N(\alpha_1,\alpha_2) + N(\alpha_1,\alpha_3) + N(\alpha_2,\alpha_3) - N(\alpha_1,\alpha_2,\alpha_3)$$
Теорема. (Формула включений и исключений)
$$N(\alpha_1',\ldots,\alpha_n') = N - N(\alpha_1) - N(\alpha_2) - \ldots - N(\alpha_n) + N(\alpha_1,\alpha_2) + \ldots + N(\alpha_{n-1},\alpha_n)-N(\alpha_1,\alpha_2,\alpha_3) - \ldots - N(\alpha_{n-2},\alpha_{n-1},\alpha_n) + \ldots + (-1)^nN(\alpha_1,\alpha_2,\ldots,\alpha_n)$$