Комбинаторные задачи с ограничениями

Задачи с ограничением на порядок

До сих пор мы рассматривали задачи, в которых на порядок элементов в комбинациях не накладывалось никаких ограничений или дополнительных условий. Либо (как в сочетаниях) порядок вообще не учитывался . Рассмотрим задачи с ограничением.

Задача 1. Укротитель хищных зверей хочет вывести на арену 5 львов и 4 тигра, при этом нельзя , чтобы два тигра шли друг за другом. Сколькими способами он может расположить зверей?

Обозначим львов буквой Л. Для тигров имеется 6 мест.

_____Л₁_____Л₂_____Л₃____Л₄_____Л₅______

Львов можно расположить $$5$$! Способами, то есть 120. На шести местах для тигров их можно расположить $$А^4_6=6 * 5 * 4 * 3 = 360$$ способами.

Общее число способов $$120 * 360 = 43200$$.

Для задачи в общем виде, если имеется: $$k$$ тигров и $$n$$ львов.

$$P_n*A^k_{n+1} = n!*(n+1)*n*(n-1)*.....(n-k+1)$$, но так как $$A^k_n = P_k* C^k_n,$$ то

$$P_nP_kC^k_{n+1}=\frac{ n!k!(n+1)!}{ k!(n+1-k)!}=\frac{ n!(n+1 )!}{ (n-k+1)!}$$

Это возможно лишь при условии , что $$n-k+1 \ge 0, k \le n+1$$

Задача 2. Строится лестница из точки $$А$$ в точку $$В$$. Расстояние $$АС=4,5м, ВС=1,5м$$. Высота ступеньки 0,3м , ширина - 0,5м или кратное 0,5 (рис 8.1). Сколькими способами можно построить лестницу ?

(рис 8.1)

Из условия видно, что лестница должна иметь $$1,5/0,3=5 \mbox{ (ступеней)}$$, при этом имеется 10 мест , где можно устроить ступеньку: $$4,5/0,5=9 \mbox{ (ступеней)}$$ и одна крайняя.

Следовательно, надо выбрать 5 мест для ступеньки из 10: $$С^5_{10}=10!/5!5!=252$$ способами.

Варианты построения показаны на рис 8.2.

(рис 8.2)

В общем случае: если $$k$$ ступенек, то лестницу можно построить $$C^k_{n+1}$$ способами.

Эта задача похожа на предыдущую; укротитель не может ставить двух тигров, а строитель - делать ступеньки удвоенной высоты. Но есть существенное различие: все звери разные, а ступеньки одинаковые, поэтому выбор у строителя меньше.

Обобщением задачи о лестнице (лестницу зашифровать 1 и 0..... ) может быть следующее: сколькими способами можно расставить $$n$$ нулей и $$k$$ единиц , чтобы две единицы не стояли рядом.

Это можно сделать $$C^k_{n+1}$$ способами.

Ограничения на порядок выбора

Задача 1. На книжной полке стоят 12 книг. Сколькими способами можно выбрать 5 из них так, чтобы никакие две из них не стояли рядом.

Зашифруем выбор 0 и 1: каждой оставленной книге поставим в соответствие 0, каждой выбранной - 1. Таким образом, имеем 5 единиц и 7 нулей и задача сводится к предыдущей.

$$C^5_{7+1}=C^5_8$$

В общем виде: Если стоит $$n$$ книг, а выбирается $$k$$ книг, не стоящих рядом, то это можно сделать

$$C^k_{(n-k)+1}$$

) Сколькими способами это можно сделать?

(рис 8.3)

Отличие от предыдущей задачи состоит в том, что рыцари сидят не в ряд, а по кругу. Но ее легко свести к случаю, когда рыцари сидят в ряд. Для этого возьмем рыцаря, например сэра Ланселота, и разомкнем круг. Все выбираемые комбинации распадаются на два класса: в одном участвует сэр Ланселот, в другом - нет. Подсчитаем сколько комбинаций входит в каждый класс.

Если сэр Ланселот отправился в поход , то его соседи справа и слева не должны участвовать. Остаются 9 рыцарей из которых надо выбрать 4. Надо проследить, чтобы среди выбранных не было врагов, то есть чтобы никакие двое не сидели рядом. Цепь разорвана следовательно:

$$C^4_{9-4+1}= C^4_6= \frac{6!}{4!2!}=15.$$

Так как сэр Ланселот не участвует в экспедиции, то его можно исключить, остается 11 рыцарей, из которых выбирается 5.

$$C^5_{11-5+1}=C^5_7=21$$. По правилу суммы всего $$C^4_6+C^5_7=15+21=36$$.

В общем случае, если по кругу расположены $$n$$ элементов, а надо выбрать $$k$$ так , чтобы в их число не попали два соседа , то это можно сделать $$C^{k-1}_{n-k-1}+C^k_{n-k}$$ способами.

Это доказывается точно так же , как и выше . Все комбинации элементов разбиваются на два класса в зависимости от одного из них (сэра Ланселота). В первом варианте будет $$C^{k-1}_{n-k-1}$$ комбинаций , а во втором $$C^k_{n-k}$$. Легко проверяется , что $$C^{k-1}_{n-k-1}+C^k_{n-k}=\frac{n}{n-k}* C^k_{n-k}$$

Доказательство:

$$\begin{array}{l} \frac{(n-k-1)!}{(k-1)!(n-k-1-k+1)!}+\frac{(n-k)!}{k!(n-k-k)!} =\frac{(n-k-1)!(n-k)k}{(k-1)!(n-2k)!(n-k)k}+\frac{(n-k)!}{k!(n-2k)!}=\\ \frac{(n-k)!*k}{k!(n-2k)!*(n-k)}+\frac{(n-k)!}{k!(n-2k)!}=C^k_{n-k}*(\frac{k}{n-k}+1)= \frac{n}{n-k}*C^k_{n-k}\\ \end{array}$$, ч. т. д.

Задачи о смещениях

Смещение элементов

Задача 1. Берутся все перестановки из пяти чисел 1,2,3,4,5 . Во скольких перестановках ни одно число не стоит на своем месте?

Решение методом включения-исключения.

Обозначим через $$\alpha$$ -свойство перестановки, заключающееся в том, что число $$\alpha$$ стоит на своем месте, а через $$N(\alpha)$$ - количество перестановок, обладающих этим свойством.

$$N(\alpha\beta)$$ - число перестановок ,обладающих свойством $$\alpha\beta$$

$$N^{(0)}$$ - число перестановок ,не обладающих ни одним из перечисленных свойств (1),(2),(3),(4) и (5), т.е. число перестановок в которых ни одно число не стоит на своем месте.

По формуле включения-исключения имеем:

$$N^{(0)} = N - N_1 - N_2 - N_3 - N_4 - N_5 + N_{12} + ... + N_{45} - N_{123} - ... - N_{345} + N_{1234} + ... + N_{2345} - N_{12345}$$

где $$N=P_5$$ - общее число всех перестановок из пяти элементов.

Задача облегчается тем ,что свойства (1),(2),(3),(4) и (5) совершенно равноправны ,поэтому ясно, что $$N_1 = N_2 = N_3 = N_4 = N_5$$. Точно так же имеем $$N_{12} = N_{23} = ... = N_{45}$$. Но число пар ,которые можно выбрать из чисел 1,2,3,4,5 - $$C^2_5$$. Свойства (1,2) и (2,1) - совпадают ,поэтому порядок нас не интересует. Точно так же имеем $$C^3_5$$ троек, $$C^4_5$$ четверок, $$C^5_5$$ пятерок. Формулу (1) перепишем:

$$N^{(0)} = N - C_5^1 N^{(1)}+ C_5^2 N^{(2)}- C_5^3 N^{(3)}+ C_5^4 N^{(4)}- C_5^5 N^{(5)}$$

где $$N^{(k)}$$ - количество перестановок ,в которых заданные $$k$$ чисел остались на своих местах.

$$N^{(1)}$$ - одно число на своем месте, остальные переставляются, т.е. $$P_4=4!=24$$. Следовательно, $$N^{(1)}=24=P_4$$.

$$N^{(2)}$$ - два числа на месте , три переставляются.

$$N^{(2)}=P_3=6$$, аналогично $$N^{(3)}=P_2=2$$ ; $$N^{(4)}=P_1=1$$ ; $$N^{(5)}=P_0=1$$. Подставляем в формулу (2).

$$N^{(0)} = P_5 - C_5^1 P_4+ C_5^2 P_3- C_5^3 P_2+ C_5^4 P_1- C_5^5 P_0=120-5*24+10*6-10*2+5*1-1*1=44.$$ Итак, в 44 случаях из 120 ни одно число не стоит на своем месте.

Совершенно так же можно найти во скольких случаях ровно один элемент стоит на своем месте. Если это первый элемент , то

$$N^{(1)} = P_4 - C_4^1 P_3+ C_4^2 P_2- C_4^3 P_1+ C_4^4 P_0=9 \mbox{ (способов).}$$

Общее количество способов ,при которых в точности один элемент стоит на своем месте, равно $$5*9=45$$ так как $$С^1_5=5$$. Итак, можно посчитать , что в точности два элемента стоят на своих местах в 20-ти случаях, три - в 10-ти случаях, четыре - в 0 случаях, пятеро - в 1-ом случае:

$$N^2 = P_3 - C_3^1 P_2+ C_3^2 P_1- C_3^3 P_0=6-3*2+3-1=2, C_5^2=\frac{5!}{2!3!}=10, => 2*10=20.$$ $$N^3 = P_2 - C_2^1 P_1+ C_2^2 P_0=2-2+1=1, C_5^3=10, => 1*10=10. N^4=P_1-C_1^1P_0=0.$$

Результат для четырех элементов объясняется тем, что если четыре элемента стоят на своем месте, то и пятый должен стоять на своем месте. Итак 120 разных способов (перестановок из 5-ти элементов) распадаются на: 44 перестановки ,в которых ни один элемент не остается на месте , 45 перестановок ,в которых ровно один элемент не меняет своего положения, 20 перестановок ,в которых ровно два элемента не меняют своего положения, 10 перестановок ,в которых ровно три элемента не меняют своего положения, 0 перестановок ,в которых ровно четыре элемента не меняют своего положения, 1 перестановки, в которой ровно пять элементов не меняют своего положения.

$$120 = 44 + 45 + 20 + +10 + 0 +1.$$

Общая задача о смещении

Число $$D_n$$ перестановок из $$n$$ элементов, при которых ни один элемент не остается в первоначальном положении:

$$D_n=P_n-C_n^1 P_{n-1}+C_n^2 P_{n-2}-…+(-1)^n C_n^n P_0 = n! \left[1-\frac{1}{1!}+ \frac{1}{2!}-…+ \frac{(-1)^n}{n!} \right]$$

Число перестановок ,в которых ровно $$r$$ элементов остаются на месте ,а остальные $$n-r$$ меняют свое положение выражается формулой

$$P_{n,r}=C_n^r P_{n-r}$$

В самом деле сначала нужно выбрать какие именно $$r$$ элементов остаются на месте. Это можно сделать $$С_n^r$$ способами , а остальные переставлять. Это можно сделать $$P_{n-r}$$ способами. По правилу произведения получаем $$C_n^r*P_{n-r}$$.

Сумма всех смещений равна

$$n! = \sum\limits_{r = 0}^n {D_{n,r} } = \sum\limits_{r = 0}^n {C_n^r D_{n - r} } \mbox{, причем }D_0=1$$

Число перестановок из $$n$$ элементов, при которых данные $$r$$ элементов смещены (остальные могут быть смещены, а могут оставаться на своих местах), выражается формулой.

$$D_{n,r^ - } = P_n - C_r^1 P_{n - 1} + C_r^2 P_{n - 2} - ... +{(-1)}^r*C_r^r P_{n-r} \mbox{ ( r^- -смещение); }$$ $$n!-C_r^1(n-1)! + C_r^2(n-2)! -…+ (-1)^r(n-r)!$$

Смещение пар

Задача 2. По пустыне идет караван из 9 верблюдов. За много дней путешествий надоедает видеть впереди себя одного и того же верблюда.

Сколькими способами можно переставить верблюдов так, чтобы впереди каждого шел другой, чем раньше?

Для решения задач перенумеруем верблюдов в первоначальном порядке от конца каравана к его началу числами: 1, 2, 3, 4, 5, 6, 7, 8, 9. Нам нужно найти все перестановки из чисел, в которых не встречаются пары $$(1,2), (2,3), (3,4), (4,5), (5,6), (6,7), (7,8), (8,9)$$.

Используем формулу включения-исключения.

Сосчитаем во скольких перестановках входит пара $$(1,2)$$. Можно предположить в этих перестановках пару за один элемент. Следовательно, всего 8 элементов, и число перестановок из 8-ми элементов, содержащих пару $$(1,2)$$ равно $$P_8$$.

Тот же результат получаем для всех 8-ми пар.

Рассмотрим перестановки, содержащие данные две пары. В этом случае объединяем элементы, входящие в две пары:

если обе пары содержат один и тот же элемент, например $$(1,\underline 2)$$ и $$( \underline 2,3) => (1,2,3), 4, 5, 6, 7, 8, 9$$, то всего $$P_7$$ перестановок.

если в парах элементы разные , например $$(1,2)$$ и $$(3,4,), \left\{ {1,2,3,4} \right\} => (1,2), (3,4), 5, 6, 7, 8, 9$$.

В обоих случаях получаем 7 новых элементов, которые можно переставлять друг с другом $$P_7$$ способами. А две пары из 8 можно выбрать $$C_8^2$$ способами. Совершенно так же доказывается ,что количество перестановок , содержащих $$k$$ пар равно $$P_{0-k}$$. При этом $$k$$ пар можно выбрать $$С _8^k$$ способами. По формуле включения-исключения получаем, что количество перестановок, не содержащих ни одной из заданных пар, равно:

$$\begin{array}{l} N^{(n)}=P_9 - C_8^1 P_8 + C_8^2 P_7 - C_8^3 P_6 + C_8^4 P_5 - C_8^5 P_4 + C_8^6 P_3 - C_8^7 P_2 + C_8^8 P_1= \\ 8!\left[9 - \frac{8}{1!}+ \frac{7}{2!}- \frac{6}{3!}+ \frac{5}{4!}- \frac{4}{5!}+ \frac{3}{6!}- \frac{2}{7!}+ \frac{8}{1!} \right] = 148329.\\ \end{array}$$

Аналогично доказывается ,что количество перестановок из $$n$$ чисел $$1, 2, ... , n$$ не содержащих ни одной из пар $$(1,2), (2,3), ... , (n-1,n)$$ выражается формулой:

$$E_n=P_n-C_{n-1}^1 P_{n-1}+ C_{n-1}^2 P_{n-2}-C_{n-1}^3 P_{n-3}+…+(-1)^{n-1} C_{n-1}^{n-1} P_1$$

Совершенно так же доказывается ,что количество перестановок из $$n$$ элементов, в которые не входят заданные $$r < n-1$$ пар, равно

$$E_n=P_n-C_r^1 P_{n-1}+ C_r^2 P_{n-2}-C_r^3 P_{n-3}+…+(-1)^r C_r^r P_{n-r}$$

если $$r>n-1$$, то$$E_n=P_n-C_{n-1}^1 P_{n-1}+ C_{n-1}^2 P_{n-2}-…-(-1)^k C_n^k P_{n-k}+…+(-1)^{n-1} C_{n-1}^{n-1} P_1=\\ = n! \left[1-\frac{1}{1!}+ \frac{1}{2!} - … + \frac{(-1)^{n-1}}{(n-1)!} \right] = n*D_{n-1}$$

Задача 3. "Карусель"

На карусели катаются $$n$$ ребят. Они решили пересесть таким образом, чтобы впереди каждого оказался другой, чем был раньше. Сколькими способами они могут это сделать?

Эта задача похожа на предыдущую, но теперь число запрещенных пар равно $$n: (1,2), (2,3), ..., (n-1,n), (n,1)$$. Кроме того, перестановки, получаемые друг из друга пересадкой по кругу, считать не будем. Поэтому из $$k$$ элементов , можно сделать $$P_k=(k-1)$$! существенно различных перестановок .

В этой задаче могут быть все $$n$$ пар, так как $$C_n^1=n$$!, а перестановок всего $$C_n^1*P_{n-2}$$. По формуле включения-исключения получаем:

$$Q_n=P_{n-1}-C_n^1 P_{n-2}+C_n^2 P_{n-3}-…+(-1)^{n-1} C_n^{n-1} P_0+(-1)^n C_n^n$$

По сравнению с формулой (5) мы берем $$n$$ пар, а не $$(n-1)$$, но так как следует учитывать вращение, то $$P_{n-1} $$,а не $$P_n$$. Формула смещения в общем виде:

$$E_n=P_n-C_{n-1}^1 P_{n-1}+ C_{n-1}^2 P_{n-2}-C_{n-1}^3 P_{n-3}+…+(-1)^{n-1} C_{n-1}^{n-1} P_1$$