Комбинаторика

Комбинаторика — это раздел математики, в котором изучают, сколько комбинаций, подчинённых тем или иным условиям, можно составить из данных объектов.

Правила произведения и суммы

Правило суммы: Если объект $A$ можно выбрать $m$ способами, а другой объект $B$ можно выбрать $n$ способами, тогда выбор "Объект $А$ или объект $В$" можно выполнить $m+n$ способами.

$$|A| = m,$$$$|B| = n,$$$$|A| + |B| = m+n$$

Правило произведения: Если объект $A$ можно выбрать $n$ способами, а другой объект $B$ можно выбрать $m$ способами, тогда пару (объект $А$, объект $В$) можно выбрать $n*m$ способами.

То есть в терминах множеств для $A$ и $B$ размерами $$|A| = m,$$ $$|B| = n,$$ тогда их декартово произведение будет размером $$|A \times B| = m*n$$

Декартово произведение

Пример 1. Сколько путей есть из точки 1 в точку 3? Пути

Их количество равно произведению количества путей из точки 1 в точку 2 на количество путей из точки 2 в 3.

$$|1 \rightarrow 3| = |1 \rightarrow 2| * |2 \rightarrow 3| = 3 * 2 = 6$$

Пример 2. Сколькими способами можно уехать из точки 2?

$$|2 \rightarrow \{1,3\}| = |2 \rightarrow 1| + |2 \rightarrow 3| = 3 + 2 = 5 $$

Задача 1: Cколько существует трёхзначных чисел, у которых есть хотя бы один нуль? (100, 804 и т.д)

Решение 1. Сколько всего трёхзначных чисел? Первая цифра трёхзначного числа должна быть от 1 до 9, а остальные две цифры от 0 до 9. Мы можем выбрать любые три подходящие числа. По правилу произведения. $$ t = |1-9| * |0-9| * |0-9| = 9*10*10 = 900$$ 2. Сколько трёхзначных чисел без нуля? Аналогично $$ \dot{t} = |1-9| * |1-9| * |1-9| = 9*9*9 = 729$$ 3. Итого По правилу суммы количество трёхзначных чисел = количеству трёхзначных чисел без нуля + количество трёхзначных чисел с нулём. Следовательно $$t_0 = t-\dot{t} = 900 - 729 = 171 $$

Следствия

Правило вычитания: Если объект $A$ может быть выбран $m$ способами, при среди этих способов есть $n$ недопустимых, то объект $A$ может быть выбран $m−n$ допустимыми способами.

Правило деления: Если объект $A$ может быть выбран $m$ способами, при этом на каждый из этих способов прихоидтся $n$ недопустимых, то объект $A$ может быть выбран $\frac{m}{n}$ допустимыми способами.

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

Перестановкой множества из $n$ элементов называется расположение этих элементов в определенном порядке.

Количество перестановок определяется формулой: $$P_n = n ∗ (n − 1) \dots 2 ∗ 1 = n!$$

Пример 3: Все различные перестановки множества из трех элементов $$\{a,b,c\}$$ — это $$\{abc,acb,bac,bca,cab,cba\}.$$ Их $3*2 = 6$ штук.

Пример 4: Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга? Как бьёт ладья
Ладья на первой горизонтали может занимать одно из 8 положений. На следующей горизонтали ладья уже не сможет находиться на той же позиции, что и на первой. У неё 7 вариантов расположения. И т.д. мы приходим к формуле $$P_8 = 8*7*\dots*1 = 8! = 40320$$

Задача 2: На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом 1-й и 2-й тома не стояли рядом?

Решение * Всего есть $P_{30}$ способов расстановки. Надо исключить из них те, которые недопустимы. * Возможны ситуации, * когда второй том стоит слева от первого и * когда второй том стоит справа от первого. То есть ошибочных ситуаций всего 2. * В каждом из этих 2-х случаев возможно $P_{29}$ случаев расстановки других книг. * Следовательно, необходимо исключить $2*P_{29}$ случаев из рассмотрения. По правилу вычитания ответ: $$30!−2∗29!.$$

Пример 5: Сколько 5-буквенных слов можно составить из слова "манна"?

  • Представим, что все буквы некоторого 5-буквенного слова разные. Тогда уникальных слов из него можно получить столько, сколько существует перестановок этих букв, $P_n=n!$
  • Пусть среди 5 букв есть 2 одинаковые. Это значит, что среди всех перестановок количество уникальных слов будет меньше. Например, из набора букв $$a_1a_2b_1c_1d_1$$ можно сделать 2 слова, в которых на местах для букв $a$ последовательность либо $a_1a_2$, либо $a_2a_1$: $$\{a_1b_1c_1d_1a_2, a_2b_1c_1d_1a_1\}.$$ С точки хрения языка эти слова одинаковы. Заметим, что количество перестановок для одной такой последовательности будет равна количеству перестановок индексов букв с одним и тем же значением. То есть в нашем случае $P_2=2!$ для каждого уникального слова.
  • По правилу деления получим для задачи с 2 одинаковыми буквами из 5 ответ $$\frac{P_5}{P_2}$$.
  • Пусть у нас есть вторая буква, которая повторяется дважды. Для $$a_1a_2b_1b_2c_1$$ теперь кроме перестановок $\{a_1a_2,a_2a_1\}$ появляются перестановки $\{b_1b_2,b_2b_1\}$. Количество одинаковых слов при этих перестановках - декартово произведение перестановок:
$$b_1b_2$$ $$b_2b_1$$
$$a_1a_2$$ $$(a_1a_2,b_1b_2)$$ $$(a_1a_2,b_2b_1)$$
$$a_2a_1$$ $$(a_2a_1,b_1b_2)$$ $$(a_2a_1,b_2b_1)$$

  • По правилу произведения неуникальных перестановок для каждого слова $P_2*P_2 = 2!*2!$, а значит ответ $$\frac{P_5}{P_2*P_2} = \frac{5!}{2!*2!}$$

Следствие о перестановках с повторениями

Сколькими способами и $n$ элементов можно выбрать $k$ элементов, чтобы первый встречался $k_1$ раз, второй $k_2$ раз, ..., $n$-ый $k_n$ раз?

$$P_{k_1,k_2,\dots,k_n} = \frac{P_n}{P_{k_1}*P_{k_2}*\dots*P_{k_n}} = \frac{n!}{k_1! * k_2! * \dots k_n!}$$

Размещения

Размещениями множества из $n$ различных элементов по $m$ элементов $(m < n)$ называются комбинации, которые составлены из данных $n$ элементов по $m$ элементов и отличаются либо самими элементами, либо порядком элементов.

Пример 6: Пусть дано множество из трех элементов $\{ a,b,c\}$. Какими способами мы можем выбрать из этих элементов два (с учётом порядка)? $$\{ab, ac, ba, bc, ca, cb\}.$$ То есть пары $ab$ и $ba$ не считаются равнозначными.

Число всех размещений множества из $n$ элементов по $m$ элементов обозначается $A^m_n$. $$A^m_n = n*(n − 1)* \dots * (n − m + 1).$$

Пример 7: Пусть у нас есть элементы $a_1, a_2, \dots ,a_n$. Будем строить наше размещение последовательно.

  1. Сначала определим $a_{i_1}$ — первый элемент размещения. Из данной совокупности $n$ элементов его можно выбрать $n$ различными способами.
  2. После выбора первого элемента $a_{i_1}$ для второго элемента $a_{i_2}$ остается $n-1$ способов выбора и т.д.
  3. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой.

Поэтому получим: $$A^m_n = n*(n − 1)* \dots *(n − m + 1).$$

Нетрудно заметить, что $$A^m_n = \frac{n!}{(n-m)!} = \frac{P_n}{P_{n-m}}$$

Пример 8: Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?

Число трёхполосных флагов из 5 цветов: $$A^3_5=5*4*3 = 60$$

Задача 3: Сколькими способами можно расставить 30 книг на двух полках, если на каждой из них помещается только по 15 томов?

Решение * Пусть мы сперва размещаем на первой полке книги. Мы можем это сделать $A^{15}_{30}$ способами. * Тогда если мы разместили на первой полке 15 книг, существует $P_{15}$ способов разместить книги на второй полке. По правилу умножения ответ: $$A^{15}_{30} * P_{15} = \frac{30!}{15!}∗15!=30!.$$

Пример 9: Есть неограниченное количество билетов в театр, в цирк и на концерт. Сколькими способами их можно раздать эти билеты четырём студентам так, чтобы каждый получил $3$ билета?

  • Первый билет у каждого студента может быть либо в театр, либо в цирк, либо на концерт. $3$ варианта на человека.
  • Второй билет у каждого студента не зависит от первого и может быть любым, снова $3$ варианта. По правилу умножения у человека может быть $3*3$ комбинации первых двух билетов. Следовательно для 3х билетов эти х комбинаций будет $3^3$.
  • Набор билетов у каждого студента не зависит от другого студента. По правилу умножения получим ответ $$(3^3)^4 = 3^{12}$$

Следствие о размещениях с повторениями

Сколькими способами можно выбрать из $n$ элементов $m$ элементов c повторениями (то есть если элементы могут быть повторно использованы)?

$$\bar{A}^m_n=n^m$$

Сочетания

Сочетаниями из $n$ различных элементов по $k$ элементов называются комбинации, которые составлены из данных $n$ элементов по $k$ элементов и отличаются хотя бы одним элементом (иначе говоря, $k$-элементные подмножества данного множества из $n$ элементов).

Пример 10: Пусть дано множество из трех элементов $\{ a,b,c\}$. Какими способами мы можем выбрать из этих элементов уникальную пару без учета порядка?? $$\{ab, ac, bc\}.$$ То есть пары $ab$ и $ba$, в отличае от размещения, считаются равнозначными.

Число всех сочетаний из $n$ элементов по $k$ элементов в каждом обозначается $C^k_n$.

Нетрудно заметить, что:

  1. $ C^0_n = 1 $ – способов не выбрать ничего из любого множества
  2. $ C^n_n = 1 $ – способов выбрать всё из любого множества
  3. $ C^1_n = n $ – способов выбрать 1 элемент из любого множества

Свойства $C^k_n$

Свойство 1: $$C^k_n = C^{n-k}_n$$ Когда мы выбираем $k$ элементов из $n$, оставшиеся $n-k$ элементов образуют подмножество, которое соответствует выбранным $k$ элементам. Таким образом, каждому $k$-элементному подмножеству данного $n$ элементного множества соответствует одно и только одно $n-k$ элементное подмножество. Поэтому всего $k$ - элементных подмножеств столько же, сколько и $n-k$ элементных.

2 из 3 1 из 3
$$\{a,b\}$$ $c$
$$\{b,c\}$$ $a$
$$\{a,c\}$$ $b$

Свойство 2: $$C^k_n=C^{k}_{n-1} + C^{k-1}_{n-1}$$

Дано множество $\{a,b,c,d,e\}$.

  • Выделим из него элемент $e$.
  • Число $k$-элементных подмножеств без $e$ = $C^{k}_{n-1}$
  • Число $k$-элементных подмножеств с $e$ =$C^{k-1}_{n-1}$

Следовательно всего $k$-элементных подмножеств $$C^k_n=C^{k}_{n-1} + C^{k-1}_{n-1}$$

Пример 11: Пусть $k=3$. Множество – $\{a,b,c,d,e\}$.

Подмножества с e: $$\{ab,ac,ad,bc,bd,cd\} \times \{e\} = \{abe,ace,ade,bce,bde,cde\}.$$ Подмножества без e: $$\{abc,abd,acd,bcd\}.$$ Все подмножества: $$\{abc,abd,abe,acd,ace,ade,bcd,bce,bde,cde\}$$

Треугольник Паскаля

Треугольник Паскаля позволяет вычислить числа $C^k_n$.

\begin{matrix} & & & & С^0_0 & & & &\\ & & & С^0_1 & & С^1_1 & & &\\ & & С^0_2 & & С^1_2 & & С^2_2 & &\\ & С^0_3 & & С^1_3 & & С^2_3 & & С^3_3 &\\ С^0_4 & & С^1_4 & & С^2_4 & & С^3_4 & & С^4_4\\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots & \end{matrix}

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

В числовом виде треугольник выглядит следующим образом:

\begin{matrix} n=0: & & & & & 1 & & & &\\ n=1: & & & & 1 & & 1 & & &\\ n=2: & & & 1 & & 2 & & 1 & &\\ n=3: & & 1 & & 3 & & 3 & & 1 &\\ n=4: & 1 & & 4 & & 6 & & 4 & & 1\\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots & \end{matrix}

Формула $C^k_n$

Теперь разберём формулу, по которой можно вычислить $C^k_n$.

$$C^k_n = \frac{n!}{k!*(n−k)!}, (0 \leq k \leq n)$$

Пример 12 Рассмотрим множество из $n$ элементов и решим двумя способами следующую задачу: сколько можно составить последовательностей из k элементов данного множества, в каждой из которых никакой элемент не встречается дважды?

Задачу можно решить несколькими способами.

1 способ. Сначала выбираем первый член последовательности, затем второй и т.д. $$x = n*(n-1)*\dots*(n-k+1) = \frac{n!}{(n-k)!} = A^k_n$$

2 способ. Выберем сначала k элементов из данного множества, а затем расположим их в некотором порядке. $$x=C^k_n *k!$$

Теперь приравняем левые части $$C^k_n*k! = \frac{n!}{(n-k)!}$$ и получим равенство $$C^k_n= \frac{n!}{k!*(n-k)!}$$

Пример 13 Сколькими способами можно в игре “Спортлото” выбрать 5 номеров из 36?

Искомое число способов: $$C^5_{36} = \frac{36!}{5!*31!} = \frac{36·35·34·33·32}{1·2·3·4·5} = 376992.$$

Пример 14 Есть 7 одинаковых билетов в театр и 3 студента, желающих их получить. Сколькими способави можно распределить билеты между студентами? Кому-то могут достаться все билеты, а кому-то ни одного.

  • Представим билеты, как некоторую последовательность нулей $$0000000$$
  • Мы знаем, что для того, чтобы распилить бревно на $3$($n$) части нужно сделать $2$ ($n-1$) надреза. Представим эти "надрезы" в последовательность билетов, как "$|$". Пример разреза: $$00|000|00,$$ или если одна часть пустая: $$0||000000.$$
  • Нам подходял все комбинации из $7+2 = 9$ нулей, в которых 2 нуля заменены на "$|$": $$000000000 \rightarrow 0|0|00000$$.
  • Задача сводится к задаче расстановки $2$ "$|$" в последовательности из $9$ элементов. Это равносильно $$C^{3-1}_{7+3-1}=\frac{(7+3-1)!}{7!*(3-1)!} = \frac{9!}{7!*2!}$$

Следствие о сочетаниях с повторениями

Сколькими способами можно выбрать $k$ элементов из $n$ одинаковых c повторениями?

$$\hat{C}^k_n = \frac{(n+k-1)!}{k!*(n-1)!} = C^{n-1}_{n + k -1}$$

Пример №1. Разложение числа на слагаемые.

Сколькими способами можно представить число $n$ в виде суммы $k$ неотрицательных слагаемых, если представления, отличающиеся только порядком слагаемых считаются различными?

Решение

Введем множество $A = {a_1, ..., a_k }$. Содержательно будем считать, что добавление элемента $a_i$ в выборку означает прибавление единицы к слагаемому с номером $i$ (полагаем, что сначала все слагаемые нулевые). Тогда условие задачи равносильно подсчету числа сочетаний с повторениями из $k$ элементов множества $A$ по $n$.

В самом деле, пусть $n = 5$, а $k = 3$. Тогда выборка $a_1, a_1, a_3, a_3, a_3$ соответствует сумме $5 = 2 + 0 + 3$. А, например, сумме $5 = 1 + 2 + 2$ соответствует выборка $a_1, a_2, a_2, a_3, a_3$. Значит, искомое число представлений равно $\hat{C_n^{k}}$. </details>

In [ ]: