МАЛЫЙ МЕХМАТ МГУ

Кружок 5 класса

Комбинаторика (доп задачи)

11.

Сколько наборов букв можно получить перестановкой из следующих слов:

а) КОТ;	г) МАМА;
б) ДЕД;	д) АУУУ;
в) БРАТ;	е) УКУШУ.

Ответы Решение

Ответы.

а) 6	г) 6
б) 3	д) 4
в) 24	е) 20

Решение. а) Все буквы разные, поэтому будет 3! = 6 вариантов их перестановки.
б) Букву Е можно поставить на одно из 3 мест, на остальных будут буквы Д, так что вариант перестановки полностью задаётся положением буквы Е, которых 3 штуки.
в) Все буквы разные, значит, 4! = 24 вариантов.
г) Будем рассуждать так же, как и когда поняли, почему надо использовать факториал для подсчёта числа перестановок. Первую букву М можно поставить на одно из 4 мест. Для каждого из этих 4 вариантов вторую букву М можно поставить на одно из оставшихся 3 мест. Для каждого из 3 · 4 = 12 этих вариантов положение букв А будет задано однозначно. Однако, поскольку буквы М на самом деле ничем не отличаются друг от друга, то каждый вариант расстановки оказался посчитан 2 раза: например, когда первая М на 1м месте, вторая М на 2м, то это не должно отличаться от варианта, когда первая М на 2м месте, а вторая — на 1м. Значит, посчитанное число нужно разделить на 2. Всего вариантов будет 12 : 2 = 6.
д) Вся расстановка полностью определяется положением буквы А, поэтому всего вариантов столько же, на сколько мест её можно поставить, то есть 4.
е) Вариант определяется положением букв К и Ш. Есть 5 способов разместить букву К, для каждого из которых букву Ш можно поставить на одно из 4 мест, оставшихся свободными, то есть всего вариантов 5 · 4 = 20.

12.

Сколько наборов букв можно получить перестановкой из следующих слов (в этой задаче факториалы от больших чисел можно оставить в ответе не посчитанными):

а) ЛЕС;	д) СЕСТРА;	и) ЗЕЛЕНОШЕЕЕ;
б) МАРТ;	е) ПАПА;	к) БИССЕКТРИСА;
в) ВЕСНА;	ж) ФАКТОРИАЛ;	л) МИКАНОТИКРОБА;
г) АПРЕЛЬ;	з) ПАРАБОЛА;	м) КОМБИНАТОРИКА.

Ответы Указание

Ответы.

а) 6;	д) 360;	и) 10! : 5! = 30240;
б) 24;	е) 6;	к) 11!: 2! : 3! = 11! : 12;
в) 120;	ж) 9! : 2;	л) 13! : 2 : 2 : 2 : 2 = 13! : 16;
г) 720;	з) 8! : 3! = 6720;	м) 13! : 2 : 2 : 2 : 2 = 13! : 16.

Указание. Первые четыре пункта решаются очевидным образом.

В следующих полезно сначала предположить, что все буквы разные. После этого заметим, что при перестановке одинаковых букв местами между собой получаются внешне одинаковые варианты, которые должны быть посчитаны за один и тот же. Например, количество способов переставить две буквы местами равно 2! = 2, так что если в слове было 2 одинаковых буквы, то каждый внешне различимый вариант оказался посчитан нами 2 раза как 2 варианта, отличающиеся перестановкой этих букв местами (когда мы считали все буквы отличающимися друг от друга).

Если было 3 одинаковых буквы (как в пункте з)), то при фиксированных остальных буквах одинаковые буквы можно переставить местами 3! способами, а внешне все эти перестановки будут выглядеть одинаково и потому должны быть посчитаны за один и тот же вариант. В таком случае каждый вариант оказался посчитан 3! раз, то есть всего вариантов будет 6! : 3! = 6! : 6 = 5! = 120.

Аналогично, в пункте и) всего будет
\(\frac{10!}{5!} = \frac{1 · 2 · 3 · 4 · 5 · 6 · 7 · ... · 10}{1 · 2 · 3 · 4 · 5} = 6 · 7 · ... · 10 = 30240\) вариантов.

В пункте к) в слове БИССЕКТРИСА есть две группы повторяющихся букв. Поступим так же, как и прежде: сначала считаем, что все буквы разные, затем учтём, что есть несколько одинаковых букв одной группы, например, С, а затем и другой, И. В итоге получим 11! : 3! : 2! вариантов. То есть, за каждую группу одинаковых букв мы делим факториал от длины слова на факториал длины этой группы.

13.

Сколько наборов букв можно получить перестановкой из следующих слов:

а) ААУ;	д) ААААУУ;	и) АУ...У (\(k\) букв У);
б) АУУ;	е) ААУУУУ;	к) ААУ...У (\(k\) букв У);
в) АААУУ;	ж) АААУУУУУ;	л) А...АУ...У (\(k\) букв А, \(n-k\) букв У);
г) ААУУУ;	з) АААААУУУ;	м) А...АУ...У (\(k\) букв У, \(n-k\) букв А).

Ответы Указание

Ответы.

а) 3;	д) 15;	и) \(k + 1\);
б) 3;	е) 15;	к) \((k+2)(k+1)/2\);
в) 10;	ж) 56;	л) \(n! : k! : (n-k)!\);
г) 10;	з) 56;	м) \(n! : k! : (n-k)!\).

Указание. в) Первая буква У может стоять на одном из 5 мест. Для каждого из этих вариантов будет 4 возможных места для второй буквы У. Расстановка обоих букв У однозначно задаёт вариант, так как всё остальное будет заполнено буквами А. При этом, так как буквы У неотличимы, то есть 2! способов поменять их местами, получая один и тот же набор, то есть каждый набор оказался посчитан 2! = 2 раза. Поэтому всего вариантов будет 5 · 4 : 2 = 5 · 2 = 10.
и) Буква А может стоять на одном из \(k + 1\) мест, а остальные обязательно будут заполнены буквами У, так что данная расстановка определяется только положением буквы А.
к) Всего мест \(k + 2\), при этом расстановка определяется только положением букв А. Сначала считаем, что две буквы А отличаются друг от друга, а затем учтём, что варианты, отличающиеся только перестановкой букв А между собой, внешне неотличимы и потому должны быть посчитаны за один.

14.

Сколькими способами можно:
а) из 5 ребят выбрать двоих;
б) из 6 ребят выбрать четверых;
в) из 7 ребят выбрать троих;
г) из \(n\) ребят выбрать \(k\)?

Решение

Решение. a) Так же, как и с буквами: выбрать первого можно 5 способами, второго — 4 способов, и при этом каждый вариант оказался посчитан 2! раз, так как порядок выбирания на самом деле неважен. Итого 5 · 4 : 2 = 5 · 2 = 10 способов.
б) 15 (выбрать 4 из 6 — то же, что выбрать двоих для невыбирания, а таких способов 6 · 5 : 2!)
в) 7·6·5:3! = 7·6·5:6 = 7·5 = 35
г) \(\frac{n!}{k! \cdot (n-k)!}\)

Последний пункт позволяет объединить следующие два способа решения задач.

При последовательном выборе есть \(n\) способов выбрать первого, при выбранном первом выбрать второго можно \(n-1\) способами, дальше третьего — \(n-2\) способами, ... \(k\)-того — \(n-(k-1) = n-k+1\) способами. При этом каждый реальный вариант выбора был посчитан \(k!\) раз, так как порядок выбирания не важен, а одну и ту же группу людей можно выбирать в разном порядке именно \(k!\) способами (\(k\) способов кого-то из выбранных выбрать первым, \(k-1\) — вторым, \(k-2\) — третьим и так далее). Итого получаем
\((n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1)) : k! = \frac{n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1) \cdot (n-k) \cdot (n-k-1) \cdot ... \cdot 1}{(n-k) \cdot (n-k-1) \cdot ... \cdot 1} : k! = \frac{n!}{(n-k)!} : k! = \frac{n!}{k! \cdot (n-k)!}\)
(Умножили и разделили на одно и то же число \((n-k) \cdot (n-k-1) \cdot ... \cdot 1\), чтобы произведение представить в более красивом виде — как частное двух факториалов.)

С другой стороны, выбор можно отобразить наглядно как написание конкретной последовательности из символов двух видов, например, Д и Н, где каждое место соответствует своему человеку, Д означает, что его выбрали, а Н — что нет. Количество комбинаций из \(k\) букв Д и \(n-k\) букв Н (потому что если всего \(n\) человек, и из них выбираем \(k\), то не выбранными останутся \(n-k\)) длины \(n\) было посчитано раньше и равно
\(n! : k! : (n-k)! = \frac{n!}{k! \cdot (n-k)!}\)

Итак, задачи можно решать разными способами, и при этом, разумеется, ответ всегда будет получаться один и тот же (потому что это ответ на задачу, он зависит от задачи, а не способа её решения). Также, вместо того, чтобы решать новую задачу заново, часто легче свести задачу к предыдущей.