Формулы комбинаторики

Последовательно найдите способы рассадить жалеющих сидть по движению, потом против движения, потом безразличных.

Четверо желающих сидеть по движению поезда можно расположить $A_5^4$ способами. Вне зависимости от их расположения, трое желающих сидеть против движения можно расположить $A_5^3$ способами. Троих безразличных по трем оставшимся местам в купе можно рассадить $P_3$ способами.

Используем правило умножения:

43 200

Разбейте все семизначные числа на два класса: в первом числа, начинающиеся на 7, а во втором числа, начинающиеся с любой цифры, кроме 7.

Разобьем все семизначные числа на два класса.

В первом классе числа, которые начинаются на цифру 7. Тогда остальные 6 вакантых мест в шестизначном числе можно занять 9 цифрами (все, кроме цифры 7). Сделать это можно $\bar{A}_9^6$ способами.

Во втором классе числа, которые не начинются на 7. В таких числах цифру 7 в числе можно расположить 6-ю способами (на любое из 6 вакантных мест). Первую цифру в числе можно выбрать 8 способами (без 7 и 0). Остальные 5 вакантных мест в числе можно занять 9 цифрами (все, кроме 7). Сделать это можно $\bar{A}_9^5$ способами.

Так как выбор первой цифры и положение цифры 7 не виляют на количество вариантов выбрать остальные цифры, то по правилу умножения получаем всего $6\cdot 8 \cdot \bar{A}_9^5$ чисел во втором классе.

Классы не пересекаются, потому что в первом все числа начинаются с 7, а во втором все числа не начинаются с 7. Общее количество цифр находим по правилу суммы:

$3 \ 365 \ 793$

Сложите варианты собрать команду без юношей, с одним юношей и так далее.

Или вычтите из всех возможных вариантов собрать команду варианты без юношей или с четырьмя юношами.

Через сумму

Команду только из девушек можно собрать $C_{12}^5$ способами. Команду из одного юноши и 4 девушек можно собрать $C_{10}^1 C_{12}^4$ способами. Команду из двух юношей и 3 девушек: $C_{10}^2 C_{12}^3$. Из трех юношей и двух девушек: $C_{10}^3 C_{12}^2$.

Все 4 группы команд не пересекаются, потому что в каждой разное количество юношей. Значит общее количество команд мы можем найти по правилу суммы:

Через разность

Можно действовать «от обратного». Найдем сначала способы составить команду без каки-либо ограничений, то есть выбрать пятерых человек из 12 + 10 = 22: $C_{22}^5$.

Теперь из всех этий вариантов вычтем составы команды только из юношей и с четырьмя юношами:

Через сумму:

Через разность:

Найдите количество спобособов выбрать пару абонентов из n, потом пару из $n-2$ и так далее. Потом избавьтесь от дубликатов.

Первую пару абонентов можно выбрать $C_n^2$ способами. Вторую $C_{n-2}^2$ способами, а третью $C_{n-4}^2$ способами. По правилу умножения находим все варианты выбрать три пары абонентов:

Но среди этих способов есть дубликаты. Например, пара абонентов $a \leftrightarrow b$ может быть выбрана во время любого из трех выборов пар: в $C_n^2$, в $C_{n-2}^2$ или в $C_{n-4}^2$.

В общем случае, любые три пары абонентов могут быть выбраны в любом порядке. Количество разных способов выбрать 3 пары абонентов равно $P_3$. Значит, каждые уникальные три пары абонентов представлены в виде $P_3$ дубликатов:

Обозначьте согласные буквой «С», а гласные «Г» и составьте из этих букв «шаблон» слова. С его помощью посчитайте количество перестановок.

Кофеварка

Пускай на первом месте в слове стоит согласная. Тогда получается такой «шаблон» для слова:

Согласные по буквам «С» можно расставить $P(2,1,1,1)$ способами. Гласные по буквам «Г» можно расставить $P(2,1,1)$ способами. Расстановвка согласных никак не влияет на количество расставить гласные. Применяем правило умножения:

Начать слово с гласной не выйдет, ведь в слове всего 4 гласные, а нужно их будет пять!

Яблоко

Так как согласных и гласных букв в слове «яблоко» одинаковое количество, то будет сразу два шаблона для слов:

В первом шаблоне получаем $P_3\cdot P(2,1)$ слов, а во втором их столько же. Получили две разные группы слов. Находим общее их количество по правилу суммы:

Для слова «кофеварка» 720 способов переставить буквы. Для слова «яблоко» — 36.

Найдите, сколько точек деления получается, если разделить сторону на n частей.

Потом найдите все возможные способы выбрать вершины треугольников и вычтите из них вырожденные треугольники, то есть такие, все вершины которых лежат на одной стороне.

Представим прямую. Одна точка деления делит ее на 2 части. 2 точки деления делят ее на 3 части. Значит $n-1$ точек деления делят ее на n частей.

Итак, на каждой стороне квадрата есть $n-1$ точек деления, то есть потенциальных вершин треугольников. Так как у квадрата 4 стороны, то все имеем $4(n-1)$ вершин.

Чтобы построить треугольник, нам нужно выбрать 3 вершины из имеющихся $4(n-1)$. Сделать это можно $C_{4(n-1)}^3$ способами.

Теперь из полученных способов надо вычесть вырожденные треугольники, когда все 3 вершины взяты на одной стороне квадрата, то есть из $n-1$ вершин:

Выберите сначала 4 девушки, а потом 4 парня или адаптируйте решение задачи «Комбинаторный оператор».

Через комбинаторные конфигурации

Выбрать 4 девушек для танцев из 12 можно $C_{12}^4$ способами. Теперь каждой девушке нужно «назначить» парня. Порядок «назначения» уже имеет значения, поэтому сделать это можно $A_{15}^4$ способами.

Выбор девушек никак не влияет на количество способов «назначить» парней, поэтому используем правило умножения:

Через правило умножения

Представим пару как два вакантных места: одно для девушки и одно для парня. Для первой пары девушку можно выбрать 12-ю способами, а парня 15-ю. По правилу умножения получаем $12\cdot 15$ способов составить первую пару.

По такой же схеме, вторую пару можно составить $11\cdot 14$ способами, третью $10\cdot 13$ и четверную $9\cdot 12$. Составление каждой пары не меняет количество способов составить следующую пару, поэтому вновь используем правило умножения:

Как и в задаче «Комбинаторный оператор», при таком составлении пар среди них есть дубликаты. Любые 4 пары могут быть составлены в любом порядке, то есть $P_4$ разными способами. Поэтому все количество способов надо поделить на $P_4$:

$16 \ 216 \ 200$

Найдите количество способов выбрать k пальцев, а затем количество способов найдеть на них k колец. Подумайте, каким числам может быть равно k.

Пускай она хочет надеть кольца на k пальцев. Выбрать эти k пальцев из 6 можно $C_6^k$ способами. Далее на уже выбранных k пальцах разместить 12 колец можно $A_{12}^k$ способами. По правилу умножения получаем всего $C_6^kA_{12}^k$ способов разместить кольца на k пальцах.

Количество пальцев с кольцами k может быть от 1 до 6 включительно. Используем правило суммы:

Если все это внимательно рассчитать и сложить, то получится $1 \ 442\ 172$. Как видим, у Кати есть огромное количество разных способов «нарядить» свои пальчики...

Сначала найдите количество способов выбрать места для четных цифр. Потом ищите количество способов расставить четные цифры по ранее выбранным местам, а затем расставляйте нечетные цифры.

Если ноль в начале числа не допускается, вычтите из всех полученных шестизначных чисел те, которые с начинаются с 0.

Выбрать 3 места для четных цифр в шестизначном числе можно $C_6^3$ способами. По выбранным трем местам эти самые четные цифры можно разместить $\bar{A}_5^3$ способами. Вне зависимости от того, как мы распределили четные цифры, на оставшиеся 3 места нечетные цифры можно расставить $\bar{A}_5^3$ способами. Используем правило умножения:

Количество чисел, начинающихся с 0 рассчитывается точно так же, только всего цифр в числе у нас уже 5, а четных цифр будет 2:

Вычитаем из всех шестизначных чисел те, что начинаются с 0:

Кстати, найти количество чисел, начинающихся на 0 можно и другим способом. На первом месте может быть любая из 10 цифр. Количество цифр, начинающихся на 0 столько же, сколько чисел, начинающихся на 1, 2 или любую другую цифру. Значит, на 0 начинается $\frac{1}{10}$ из всех шестизначных чисел:

Всего «шестизначных» чисел:

Настоящих шестизначных чисел, не начинающихся с 0:

Сначала расположите в ряд только львов. Потом посмотрите, как можно разместить тигров.

Только львов в ряд можно расставить $P_5$ способами.

Между львами есть 4 «вакантных» места для тигров, плюс еще по месту до львов и после. Всего 6 возможных положений, которые можно распределить по тиграм $A_6^4$ способами.

Расположение львов никак не влияет на количество вариантов расположить тигров. Поэтому можно использовать правило умножения:

Сначала найдите способы расставить черные книги. Потом красные. Используйте правило умножения.

Черные книги в начале полки можно расположить $P_m$ способами. Вне зависимости от того, как мы черные книги расставим, красные книги за черными можно расположить $P_n$ способами. По правилу произведения получаем всего $P_m P_n = m!n!$ способов.

Если черные книги стоят рядом, но не обязательно первыми, то есть $(n+1)$ способов их «пачкой» разместить где-то на книжной полке: начиная с первых мест (первый способ) и смещая вправо на одну книгу (еще n способов):

Если черные книги стоят на первых местах:

Если черные книги не обязательно на первых местах:

Как вариант, можете найти варианты расставить все 5 букв без ограничений и догадаться, сколько из них нарушают условие задачи...

Для ответа на второй вопрос работайте с парой букв АБ как с единым и неделимым целым.

Сначала ответим на второй вопрос, потому что он проще. Если выступает сначала А, а потом сразу Б, то эту «склеенную» пару букв можно расположить в списке 4 способами. При любом из этих способов оставшиеся три буквы по трем местам в списке можно расположить $P_3$ способами. Применяем правило умножения:

А вот к ответу на первый вопрос можно найти прийти разными путями:

Через перестановки

Без учета ограничений задачи буквы по списку можно расположить $P_5 = 5!$ способами. В любом способе есть буквы А и Б. На каждый нужный нам вариант, где А стоит до Б найдется ровно один вариант, в котором эти буквы стоят наоборот, нарушая условие.

Поэтому под условие задачи подходит только половина из всех 5! способов:

Через сочетания

Всего в списке можно выбрать $C_5^2$ неупорядоченных пар мест. Каждую из этих пар можно представить как вариант расположения букв А и Б. Оставшиеся три буквы по трем местам в списке можно расположить $P_3$ способами:

Через правило суммы

Если А стоит на первом месте, то букву Б можно расположить 4 способами в списке после А и еще $P_3$ способов расставить три оставшиеся буквы по трем местам.

Если A стоит на втором месте, то букву Б можно расположить 3 способами в списке после А и еще $P_3$ способов расставить три оставшиеся буквы по трем местам.

Продолжая эту логику и используя правило сложения находим все способы:

60 способов при условии, что выступит А раньше Б.
24 способа, если Б выступает сразу после А.

Найдите количество всех слов, которые можно составить из букв. Потом найдите количество слов с четырьмя «е» подряд. Ответом на задачу будет разница между двумя найденными числами.

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

Четыре «склеенные» буквы «е» в восьми вакантных местах можно разместить пятью способами. В любом из этих способов оставшиеся четыре согласные можно разместить по четырем местам $P_4 = 4!$ способами. Применяем правило умножения:

Вычитаем из всех возможных слов слова с четырьмя «е» подряд и так находим количество слов, в которых «е» не идет четыре раза подряд:

1560

Расставьте сначала все буквы, кроме «о». Потом подумайте, куда и как можно дописать «о».

Для начала найдем все варианты выписать буквы вообще без «о». Таких букв всего 11, а количество способов выписать их можно найти при помощи перестановок с повторениями:

Теперь между этими буквами, а также слева и справа можно вписать ровно по одной букве «о». Всего 12 вакантных мест для 7 букв «о». Выбрать эти 7 мест из 12 для букв «о» можно с помощью сочетаний: $C_{12}^7$.

Количество вариантов расставить буквы «не о» никак не влияет на количество вариантов расставить буквы «о», поэтому можно использовать правило произведения:

Повторите решение задачи про буквы «о». Потом сделайте поправку на то, что гласные разные.

Повторяем решение задачи про буквы «о». Всего $P(2,1,1)$ способов расставить согласные и $C_{5}^4$ способов выбрать места для гласных.

Так как гласные разные, то по выбранным $C_5^4$ местам их можно расставить $P(2,1,1)$ способами. Применяем правило умножения:

Пронумеруем все точки натуральными числами от 1 до n. Тогда любой многоугольник с вершинами в этих точках можно представить как набор чисел:

Количество всех k-угольников находим по формуле размещений без повторений. Оно равно $A_n^k$. Но среди этих размещений есть множество дубликатов.

Во-первых, начать перечислять k вершин k-угольника можно с любой вершины. Наборы вершин 123, 231 и 312 обозначают один и тот же многоугольник, просто в первом случае его начали строить с вершины 1, во втором с 2, а в третьем с 3.

Всего таких, как их называют, «циклических перестановок», k штук, потому что начать строить можно с любой из k вершин. Каждый k-угольник имеет k таких дубликатов, поэтому общее количество $A_n^k$ надо поделить на k:

Во-вторых, каждый набор чисел можно перечислить «в обратном» порядке. Наборы 1234 и 4321 обозначают один и тот же многоугольник. Такой «обратный» дубликат имеет каждый k-угольник, поэтому общее количество надо поделить на 2:

k в нашей формуле количества k-угольников может быть любым числом начиная с 3 (треугольники) и заканчивая n (n-угольники). По правилу суммы находим количество всех возможных многоугольников:

Из всех $A_n^k$ размещений вершин в разном порядке выпуклый k-угольник получится только если вершины перечислять строго по возрастанию. Например: 1234 — выпуклый, а 1324 — невыпуклый. Сделать это можно одним способом, поэтому вместо размещений используем сочетания: $C_n^k$. С дубликатами история точно такая же. В итоге получаем количество всех возможных выпуклых многоугольников:

Количество всех возможных многоугольников:

Количество выпуклых многоугольников:

Выбирать рабочие дни надо из дней, которые не заняты отдыхом.

После каждого рабочего дня Жанна отдыхает минимум 4 дня. Значит в месяц Жанна обязательно должна отдыхать $5 \cdot 4 = 20$ дней.

В месяце 30 дней, причем какие-нибудь 20 из них мы трогать не можем, они заняты отдыхом. Тогда выбрать 5 рабочих дней можно только из 30 - 20 = 10 дней. Сделать это можно $C_{10}^5$ способами.

$C_{10}^5 = 252$

Эта задача является красивой иллюстрацией получения правильного ответа без какого-либо «моделирования» возможных расписаний — чисто из комбинаторных соображений.

Да, мы получили верный ответ — 252 возможных расписания. Но вот перечислить их задача уже нетрививальная.

Выберите одного рыцаря и посмотрите, сколькими способами можно выбрать оставшихся 4-х.

Еще можете выделить одного рыцаря, назвать его A и рассмотреть два класса: отряды с рыцарем A и отряды без рыцаря A.

В любом из этих двух подходов вам понадобится воспользоваться результатами задачи «Потехе время, а работе час».

Решение «по кругу»

Первого рыцаря можно выбрать 12-ю способами.

Вне зависимости от выбранного первого рыцаря нам нужно выбрать (без разницы в каком порядке) еще 4 рыцаря, НО:

• 1 рыцаря мы только чтобы выбрали.

• Ее 2-е его соседей нельзя выбирать, ведь они противники уже выбранного рыцаря.

• Между каждыми из 4 рыцарей обязательно должен быть «пробел», чтобы не взять противников. Всего 3 «пробела». (см. решение «Потехе время, а работе час»)

Поэтому выбрать оставшихся 4 рыцарей можно $C_{12 - 1 - 2 -3}^4 = C_6^4$ способами.

Используем правило умножения:

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

Решение «в ряд»

Возьмем какого-нибудь произвольного рыцаря и назовем его A. Будем рассматривать два класса:

1. Все способы собрать отряд вместе с рыцарем A

2. Все способы собрать отряд без рыцаря A

В классе с рыцарем A мы круг по сути разорвали круг и выстроили рыцарей в ряд, начиная с A:

В этом классе нужно выбрать 4 рыцаря из 9, но между рыцарями обязательно должен быть как минимум один промежуток, значит суммарно 3 промежутка между 4 рыцарями:

За пояснениями про промежутки и построение подобных сочетаний смотрите решение задачи «Потехе время, а работе час».

В классе без рыцаря A осталось 11 рыцарей, которых теперь тоже можно выстроить в ряд:

Среди них надо выбрать 5 рыцарей, но тоже с обязательным минимальным разрывом в одного рыцаря, то есть с 4 пропусками:

Так как классы с рыцарем A и без него не пересекаются, можно использовать правило суммы и найти все способы собрать отряд из 5 рыцарей:

36

Это задача — частный случай задачи о рыцарях короля Артура, только в этот раз всего рыцарей n, а выбираем из них мы 3. Найдите, сколько останется доступных для выбора вершин после выбора любой первой вершины треугольника.

Все дейсвтия точно такие же, как и при решении задачи о рыцарях короля Артура, только в этот раз всего рыцарей n, а выбираем из них мы 3.

Решение «по кругу»

Решение «в ряд»

Посчитайте, сколько вершин n-угольника нужно задействовать для построения k-угольника.

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

Таким образом для построения k-угольника нам необходимо k вершин самого k-угольника и еще k нетронутых вершин. И в сумме это должно быть не больше имеющихся в распоряжении n вершин n-угольника:

Так как k это целое число, то его максимум это целая часть от $\frac{n}{2}$:

Выпишите только гласные и найдите количество способов выбрать между и по бокам от них места под слагаемые. Заполните эти места слагаемыми.

Выпишем только гласные слова «фацетия», а вакантные места для согласных будем отмечать цифрами в квадратах:

Всего 5 вакантных мест. Нам нужно выбрать из них 3 места под слагаемые, причем места могут повторятся, но их порядок значения не имеет. Количество способов это сделать можно посчитать по формуле сочетаний с повторениями: $\bar{C}_5^3$.

Позиции для слагаемых мы выбрали. Вне зависимости от выбранных позиций три слагаемых по ним мы можем разместить $P_3$ способами. Используем правило умножения:

Со словом «параллелизм» алгоритм точно такой же, вот только там некоторые слагаемые повторяются, поэтому надо использовать формулу перестановок с повторениями:

Слово «фацетия»:

Слово «параллелизм»:

Сначала найдите количество способов составить конструкцию «гссг», где «г» — гласная, а «с» — согласная. Затем встраивайте ее в итоговое слово.

Согласно условию в итоговом слове должна обязательно присутствовать конструкция следующего вида:

Гласные по местам «г» можно разместить $P_2$ способами. Вне зависимости от размещения гласных, согласные по местам «с» можно разместить $A_4^2$ способами. По правилу умножения находим все способы составить такую конструкцию:

Это сочетание из 4-х букв в итоговое слово можно встроить 3-мя способами:

Наконец, оставшиеся два места можно заполнить двумя оставшимися согласными $P_2$ способами:

288

Сначала поставьте три согласных на четные позиции, а затем расставьте все остальные буквы.

Сначала разместим 3 слагаемых из 5 по четным позициям. Сделать это можно $A_5^3$ способами. Остальные 5 букв расставляем по 5 оставшимся в слове местам $P_5$ способами.

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

7200

Для ответа на первый вопрос из всех способов расставить буквы нужно вычесть варианты с тройными «о». Для ответа на второй вопрос расставьте слагаемые и выберите «позиции» для букв «о».

Всего буквы можно расставить $P(3,1,1,1)$ способами. Три согласные можно расставить $P_3$ способами и 4 способа встроить между ними (2) и по бокам (еще 2) «склеенную» тройку букв «о». Вычитаем из всех способов варианты с тройной «о»:

Второй вопрос еще проще. Опять расставляем три согласные $P_3$ способами. Теперь для букв «о» нужно выбрать 3 позиции из 4-х имеющихся (2 между согласными и 2 по бокам). Сделать это можно $C_4^3$ способами.

Расстановка согласных никак не влият на способы выбрать позиции для букв «о», поэтому для нахождения всех способов можно использовать правило умножения:

96 способов без тройных «о» и 24 без двойных «о».

Все возможные пятизначные числа разбейте на группы по количеству одинаковых цифр в их записи. Например, группа (2, 1, 1, 1) означает, что в пятизначном числе 2 одинаковые цифры и 3 уникальные (как в числе 11234).

Таких групп всего 7:

1. (1, 1, 1, 1, 1)

2. (2, 1, 1, 1)

3. (2, 2, 1)

4. (3, 1, 1)

5. (3, 2)

6. (4, 1)

7. (5)

Найдите количества пятизначных чисел в каждой из них.

Потом из общего количества чисел вычтите количество чисел с тремя тройками.

Сначала нам нужно найти, а сколько вообще можно составить из данных цифр пятизначных чисел.

Для этого все возможные пятизначные числа разобьем на группы по количеству одинаковых цифр в их записи. Например, группа (2, 1, 1, 1) означает, что в пятизначном числе 2 одинаковые цифры и 3 уникальные (как в числе 11234).

Найдем все группы:

1. (1, 1, 1, 1, 1)

2. (2, 1, 1, 1)

3. (2, 2, 1)

4. (3, 1, 1)

5. (3, 2)

6. (4, 1)

7. (5)

Группа под номером 1 пустая, так как у нас нет 5 разных цифр. Так же пустыми являются группы под номерами 7 и 6, потому что у нас в распоряжении нет ни 5, ни 4 одинаковых цифр (у нас максимум три одинаковые цифры 3).

Выходит, все требуемые пятизначные числа можно разбить на 4 группы:

• (2, 1, 1, 1)

• (2, 2, 1)

• (3, 1, 1)

• (3, 2)

Подсчет чисел в группах

Для удобства запишем имеющиеся цифры, расположив дубликаты рядом друг с другом:

Будем идти по порядку. Начнем с группы (2, 1, 1, 1). Две одинаковые цифры можно взять либо из единиц, либо из двоек, либо из троек, то есть всего 3 способа.

Вне зависимости от выбранных двух одинаковых цифр построить пятизначное число можно $P(2,1,1,1)$ способами (две одинаковые цифры, и по одному экземпляру всех остальных цифр). По правилу умножения находим количество чисел в группе (2, 1, 1, 1) :

Теперь группа (2, 2, 1). Если единственной уникальной цифрой будет 4, то по два дубликата можно взять 3-мя способами (1122, 1133, 2233). Если уникальной цифрой выбрать 1, 2 или 3, то в каждом из этих трех вариантов дубликаты можно выбрать единственным способом. Получается следующая ситуация:

Теперь группа (3, 1, 1) . Тут три дубликата можно взять только тройками. А вот 2 разные цифры можно выбрать тремя способами (12, 14, 24). По правилу умножения находим количество пятизначных чисел в этой группе:

Наконец, группа (3,2). Опять же, три дубликата можно взять только тройками. А вот два других дубликата можно взять двумя способами (11, 22).

Количество пятизначных чисел

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

Для выражений с P используем формулу перестановок с повторениями:

Количество чисел с тремя тройками

Найдем количество чисел с тремя тройками. Пускай у нас уже есть три цифры 3 в числе. Осталось расположить еще две цифры. Расположить их можно либо по бокам, либо обе до, либо обе после — всего 3 варианта.

Прямым перебором в порядке возрастания перечислим все возможные варианты занять эти два места:

Всего 8 способов заполнит два места и 3 возможных расопложения этих двух мест. То есть чисел с тремя тройками всего $3\cdot 8 = 24$.

Ответ на задачу

Вычитаем из количества всех пятизначных чисел числа с тремя тройками:

416