Сочетания

Научимся составлять сочетания и считать их количество. Выведем одни из самых полезных формул в комбинаторике. С этими знаниями поймем, стоит ли участвовать в лотереях!

Покрасочные работы

Сколькими способами можно выбрать три различных краски из имеющихся пяти различных красок?

Решение

Выбрать надо три различные краски, поэтому повторяться они не могут. Важны только выбранные цвета, а не их порядок. Поэтому каждый выбор трех красок можно рассматривать как сочетание из 5 доступных красок по 3 «вакантным местам» для красок. Количество этих сочетаний находим по формуле:

C53=5!(53)! 3!=452=10C_5^3 = \frac{5!}{(5-3)! \ 3!} = \frac{4\cdot 5}{2} = 10
Ответ

C53=10C_5^3 = 10

Возвращение ладей

Сколькими способами на шахматную доску 8×88 \times 8 клеток можно поставить 8 одинаковых ладей? А если расставлять k ладей на поле размером n×mn\times m клеток?

Решение

Так как ладьи одинаковые, то порядок их расположения в 8 клетках не имеет значения. Будем каждой ладье назначать свою клетку. Одну клетку можно назначить только один раз.

При таких условиях каждую расстановку ладей можно рассматривать как сочетание из 64 доступных для выбора клеток по 8 ладьям. Находим количество сочетаний по формуле:

C648=(648)=4 426 165 368C_{64}^8 = \binom{64}{8} = 4 \ 426 \ 165 \ 368

В общем случае у нас будет mnm\cdot n клеток, которые надо распределить по k одинаковым ладьям. Количество способов это сделать:

Cmnk=(mn)!(mnk)! k!C_{mn}^k = \frac{(mn)!}{(mn - k)! \ k!}
Ответ

8 ладей на поле 8×88\times 8:

C648=(648)=4 426 165 368C_{64}^8 = \binom{64}{8} = 4 \ 426 \ 165 \ 368

k ладей на поле m×nm\times n:

Cmnk=(mn)!(mnk)! k!C_{mn}^k = \frac{(mn)!}{(mn - k)! \ k!}

Книжный обмен

У одного человека есть 7 книг по математике, а у другого — 9 книг. Сколькими способами они могут обменять одну книгу одного на одну книгу другого? А 3 книги одного на 3 книги другого?

Указание

Воспользуйтесь правилом умножения.

Решение

Первый человек может 7-ю способами выбрать книгу для обмена. Вне зависимости от выбранной им книги, второй человек свою книгу для обмена может выбрать 9-ю способами. По правилу умножения получаем 79=637\cdot 9 = 63 способа обменяться.

Запишем то же самое, но используя формулу количества сочетаний:

C71C91=63C_7^1 C_9^1 = 63

Если же обмен происходит по три книги, причем порядок выбранных для обмена книг роли не играет, то мы по-прежнему работаем с сочетаниями:

C73C93=2940C_7^3 C_9^3 = 2940
Ответ

При обмене одной книгой C71C91=63C_7^1 C_9^1 = 63 варианта. При обмене трех книг C73C93=2940C_7^3 C_9^3 = 2940 вариантов.

Грузоперевозки

Сколькими способами можно вывезти со склада 12 ящиков на двух одинаковых машинах, если на каждую машину грузят по 6 ящиков?

Указание

Исопльзуйте формулу сочетаний без повторений.

Решение

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

C126=(126)=12!6! 6!=924C_{12}^6 = \binom{12}{6} = \frac{12!}{6! \ 6!} = 924

Всего 924 способа загрузить одну машину. Вне зависимости от выбранного способа загрузки, во вторую машину нужно загрузить 6 оставшихся ящиков, а сделать это можно только одним образом — загрузить их все.

Так как машины одинаковые, то нет никакой разницы, грузим мы ящики 924 способами на первую машину или на вторую. Ведь после загрузки их можно просто поменять местами и вот вторая машина уже стала первой.

Итого, в целом все ящики на двух одинаковых машинах можно вывезти 924 способами, если считать две машины неотличимыми друг от друга.

Ответ

924

Динамо бежит?

Из спортивного клуба, насчитывающего 30 членов, надо составить команду из 4 человек для участия в беге на 1000 м. Сколькими способами это можно сделать?

А сколькими способами можно составить команду из 4 человек для участия в так называемой «шведской эстафете» 100 + 200 + 400 + 800?

Указание

В команде для эстафеты, в отличие от бега на 1000 метров, у каждого бегуна есть своя конкретная дистанция, которую он должен пробежать.

Решение

Когда мы выбираем членов команды для забега на 1000 метров, нет никакой разницы, как именно мы производим выбор. Все равно каждый из бегунов бежит одну и ту же дистанцию. Поэтому каждый вариант составить команду является сочетанием из 30 кандидатов по 4 местам в команде. Находим количество сочетаний по формуле:

C304=(304)=30!(304)! 4!=27 405C_{30}^4 = \binom{30}{4} = \frac{30!}{(30 - 4)! \ 4!} = 27 \ 405

В эстафете же уже внутри команды появляется разбивка на 4 разные дистанции. Поэтому каждый вариант составить команду является размещением без повторений из 30 кандидатов по 4 разным пробегаемым дистанциям в команде. Находим количество размещений по формуле:

A304=30!(304)!=657 720A_{30}^4 = \frac{30!}{(30 - 4)!} = 657 \ 720

Кстати, этот же результат можно получить другим способом. Сначала собраем команду без разбивки по дистанциям: C304C_{30}^4. Но в каждом этом составе есть 4! способа назначить участникам дистанции (формула перестановок). Итоговое количество вариантов собрать команду для эстафеты получаем по правилу умножения:

C3044!=30!(304)! 4!4!=A304C_{30}^4 \cdot 4! = \frac{30!}{(30 - 4)! \ \cancel{4!}} \cdot \cancel{4!} = A_{30}^4
Ответ

Составить команду для бега на 1000 метров можно C304=27 405C_{30}^4 = 27 \ 405 способами, а для эстафеты A304=657 720A_{30}^4 = 657 \ 720 способами.

Точки пересечения прямых

На плоскости проведены n прямых линий, из которых никакие две не являются параллельными и никакие три не пересекаются в одной точке. Сколько точек пересечения имеют эти прямые?

Указание

Из условия получается, что любая пара прямых образует точку пересечения. Используйте этот факт.

Решение

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

Сначала сделаем несколько важных выводов из условия задачи:

  1. Любые две прямые обязательно пересекаются друг с другом

  2. Через каждую точку пересечения всегда проходят только две прямые

Первое выполняется, потому что в противном случае прямые были бы параллельными, что запрещено условием. Второе выполняется, потому что никакие три (а значит и никакие четыре, пять и так далее) прямые не пересекаются в одной точке.

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

Неупорядоченные пары прямых это буквально сочетания из n прямых по 2 местам в паре. Найдем их количество по формуле:

Cn2=(n2)=n!(n2)! 2!=n(n1)2C_n^2 = \binom{n}{2} = \frac{n!}{(n-2)! \ 2!} = \frac{n (n-1)}{2}

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

Выберем две прямые. Первую можно выбрать n способами. Вне зависимости от сделанного выбора вторую прямую можно выбрать (n1)(n-1) способами. По правилу произведения получаем n(n1)n \cdot (n-1) способов выбрать две прямые, а значит столько же точек пересечения.

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

n(n1)2\frac{n(n-1)}{2}

Через арифметическую прогрессию

Нариусем первую прямую. Пока что 0 точек пересечения. Добавим вторую прямую. К нулю исходных точек добавится одна точка пересечения с одной прямой, которая уже была нарисована. Добавим третью прямую. Образуется еще две новые точки пересечения с двумя уже нарисованными прямыми в дополнение к уже одной имеющейся точке.

Продолжаем этот процесс. В конечном итоге добавление n-ой прямой обрзаует еще (n1)(n-1) точек пересечения с (n1)(n-1) уже нарисованными прямыми, с сохранением предыдущих точек! Получается следующая формула количества точек пересечения:

0+1+2++(n2)+(n1)0 + 1 + 2 + \ldots + (n-2) + (n-1)

Опустим ни на что не влияющий 0 и понимаем, что это сумма (n1)(n-1) членов самой банальной арифметической прогрессии с разностью d=1d=1 и первым членом, равным 1. Найдем, чему равна эта сумма по формуле:

1+2++(n1)=n(n1)21 + 2 + \ldots + (n-1) = \frac{n(n-1)}{2}
Вставить ссылку на арифметическую прогрессию!
Ответ
Cn2=(n2)=n!(n2)! 2!=n(n1)2C_n^2 = \binom{n}{2} = \frac{n!}{(n-2)! \ 2!} = \frac{n (n-1)}{2}

Вечерний театр

Труппа состоит из 10 артистов. Сколькими способами можно выбирать из нее в течении двух вечеров по 6 человек для участия в спектаклях так, чтобы эти составы не совпадали друг с другом?

Указание

Во второй вечер может выступать то же самое количество составов, что и в первый, кроме одного — того, что играл в первый вечер.

Решение

Каждый состав для спектакля является неупорядоченным набором из 6 артистов. Поэтому состав по сути является сочетанием из 10 артистов по 6 местам в составе. Найдем количество составов по формуле: C106C_{10}^6.

Но это количество составов на первый вечер. Следующим вечером должен выступать другой состав, то есть вариантов по-прежнему C106C_{10}^6 за исключением уже сыгравшего состава: C1061C_{10}^6 - 1.

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

C106(C1061)=43 890C_{10}^6 \cdot \left(C_{10}^6 - 1\right) = 43 \ 890
Ответ
C106(C1061)=43 890C_{10}^6 \cdot \left(C_{10}^6 - 1\right) = 43 \ 890

Фруктовые дни

У мамы два одинаковых яблока и три одинаковых груши. Каждый день в течение 5 дней она выдает сыну по одному фрукту. Сколькими способами это может быть сделано? Решите аналогичную задачу, если если яблок n, а груш k.

Указание

Посчитайте количество способов выбрать пару дней, когда сын получает яблоки.

Решение

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

Найдем количество способов выбрать «яблочные» дни, то есть дни, когда сын получал яблоко. Для этого посчитаем количество сочетаний из 5 дней по 2 «яблочным» дням по формуле: C52=10C_5^2 = 10.

Остальные 3 дня в любом из этих 10 вариантов сын получает груши. Но так как груши одинаковые, то никаких новых способов раздать фрукты это не порождает. Получается C52C_5^2 и есть все способы, которыми мать может раздать фрукты.

Кстати, эту задачу можно решить и наоборот, найдя «грушевые» дни. Получится тот же самый ответ: C53=10C_5^3 = 10. В этом смысле задача является хорошей иллюстрацией следующего свойства сочетаний:

Cnk=CnnkC_n^k = C_n^{n-k}

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

Задачу можно решить и другим способом. Выпишем в ряд номера всех пяти дней. Над каждым днем можно указать букву «Я» или «Г», в зависимости от фрукта, который получает сын. Например:

1Г, 2Г, 3Я, 4Г, 5Я\overset{Г}{1}, \ \overset{Г}{2}, \ \overset{Я}{3}, \ \overset{Г}{4}, \ \overset{Я}{5}

Тогда каждый вариант раздать фрукты является перестановкой с повторениями из 5 этих самых фруктов. Находим количество этих вариантов по формуле:

P(3, 2)=(3+2)!3! 2!=10P(3, \ 2) = \frac{(3+2)!}{3! \ 2!} = 10
Ответ
C52=C53=10C_5^2 = C_5^3 = 10

Роковая ошибка Олега

Олег решил задачу «Фруктовые дни» следующим образом. Он выписал все фрукты в один ряд, а над ними стал проставлять номера дней. Например:

Я2, Я1, Г4, Г5, Г3\overset{2}{Я}, \ \overset{1}{Я}, \ \overset{4}{Г}, \ \overset{5}{Г}, \ \overset{3}{Г}

Каждый вариант раздать фрукты является размещением без повторений из 5 дней по 5 фруктам. Олег получает ответ: A55=120A_5^5 = 120.

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

Указание

Олег не учел «одинаковость» фруктов.

Решение

Ошибка Олега заключается в том, что в его решении все фрукты друг от друга отличаются, хотя в задаче четко говорится, что яблоки и груши одинаковые.

Из-за этого в его 120 вариантах раздать фрукты встречаются и два вот таких:

Я1, Я2, Г3, Г4, Г5Я2, Я1, Г3, Г4, Г5 \overset{1}{Я}, \ \overset{2}{Я}, \ \overset{3}{Г}, \ \overset{4}{Г}, \ \overset{5}{Г} \\ \overset{2}{Я}, \ \overset{1}{Я}, \ \overset{3}{Г}, \ \overset{4}{Г}, \ \overset{5}{Г}

По условию задачи это должны быть два одинаковых варианта, ведь яблоки он в обоих случаях получает в первые два дня. А у Олега эти варианты разные.

Городки

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

Указание

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

Решение

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

Есть C32C_3^2 способов выбрать пару юношей для первой команды. Последний оставшийся юноша единственным образом отправляется во вторую команду.

Чтобы завершить состав первой команды, в нее надо добавить пару девушек. Это можно сделать C52C_5^2 способами, вне зависимости от выбранной пары юношей. По правилу умножения получаем все способы укомплектовать первую команду:

C32C52=30C_3^2 C_5^2 = 30

Все оставшиеся девушки, прямо как и оставшийся юноша до этого, единственным образом отправятся во вторую команду.

Так как один оставшиеся 1 юноша и 3 девушки автоматически идут в противоположную команду, не порождая новых вариантов, получается, что все способы разбиться на две команды по сути определяются лишь способами составить всего одну команду!

Ответ
C32C52=30C_3^2 C_5^2 = 30

Президиум и делегация

Из состава конференции, на которой присутствуют 52 человека, надо избрать президиум в составе 5 человек и делегацию в составе 3 человек. Сколькими способами может быть произведен выбор, если члены президиума могут войти в состав делегации? А если не могут?

Указание

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

Решение

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

Разберем вариант, когда члены президиума могут быть и членами делегации. Есть C525C_{52}^5 сопособов выбрать членов президиума и вне зависимости от выбранных людей есть еще C523C_{52}^3 способов выбрать членов делегации. По правилу умножения получаем общее число способов выбрать и президиум, и делегацию:

C525C523C_{52}^5 C_{52}^3

Если же члены президиума не могут быть членами делегации, то последних можно выбирать уже не из 52 человек, а из 47, потому что 5 человек уже задействованы в президиуме:

C525C473C_{52}^5 C_{47}^3

На второй вопрос можно ответить и другим способом. Сначала C528C_{52}^8 способами выбираем 8 человек, а потом уже из них C83C_8^3 способами выбираем членов делегации, или, что то же самое, C85C_8^5 способами выбираем членов президиума:

C528C83=C528C85C_{52}^8 C_8^3 = C_{52}^8 C_8^5
Ответ

Если члены президиума могут участвовать в делегации:

C525C523C_{52}^5 C_{52}^3

Если не могут:

C525C473=C528C83=C528C85C_{52}^5 C_{47}^3 = C_{52}^8 C_8^3 = C_{52}^8 C_8^5

Битва Древних

В компьютерной игре «Dota 2» между собой сражаются две команды: «Силы Света» и «Силы Тьмы». Из 124 доступных для выбора героев в каждую команду выбирается по 5 героев. Брать одних и тех же героев нельзя.

Сколькими различными способами герои могут распределиться по командам? Могли ли сразиться между собой все возможные пятерки героев, если за время существования игры было сыграно около 8 миллиардов матчей?

Указание

Найдите количество вариантов укомплектовать героями сначала одну команду, а после этого вторую.

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

Решение

Начнем набирать героев в команду сил Света (без разницы с какой из двух начать). Всего 5 мест в команде, по которым в любом порядке нужно пять из 124 героев.

При таких условиях укомплектованную команду можно рассматривать как сочетание из 124 героев по 5 местам в команде. Количество таких сочетаний находим по формуле и оно равно C1245C_{124}^{5}. С командой сил Тьмы логика такая же, но к этому моменту героев осталось 119, поэтому всего C1195C_{119}^{5} вариантов собрать команду.

Каждый из C1245C_{124}^{5} вариантов укомплектовать первую команду всегда порождает C1195C_{119}^{5} вариантов укомплектовать вторую. Значит мы можем использовать правило умножения, чтобы найти все возможные распределения героев по командам:

C1245C1195C_{124}^{5} \cdot C_{119}^{5}

Это примерно 41 квадрилионов вариантов, то есть 411015\approx 41 \cdot 10^{15}.

Для ответа на второй вопрос проведем преобразования:

C1245C1195=124!119! 5!119!114! 5!==115116120124120==115119121124 C_{124}^{5} \cdot C_{119}^{5} = \frac{124!}{\cancel{119!} \ 5!} \cdot \frac{\cancel{119!}}{114! \ 5!} = \\ = \frac{115 \cdot 116 \cdot \ldots \cdot \cancel{120} \cdot \ldots \cdot 124}{\cancel{120}} = \\ = 115\cdot \ldots 119 \cdot 121 \cdot \ldots 124

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

100100100=1009=(102)9=1029=1018100 \cdot 100 \cdot \ldots \cdot 100 = 100^{9} = \left(10^{2}\right)^9 = 10^{2\cdot 9} = 10^{18}

Получили число с 18 нулями в то время как в сыгранных 8 миллиардах игр нулей всего 9:

115119121124>1018>8109115\cdot \ldots 119 \cdot 121 \cdot \ldots 124 > 10^{18} > 8\cdot 10^{9}

Даже если каждая из уже сыгранных игр была бы с уникальным распределением героев по командам, до полного перебора всех вариантов еще невообразимо далеко.

Ответ
C1245C1195411015C_{124}^{5} \cdot C_{119}^{5} \approx 41 \cdot 10^{15}

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

Примечание

Кстати, если вообще убрать разделение на команды и набирать по 10 героев на матч, то даже в этом случае вариантов получится C12410C_{124}^{10} и это все еще сильно больше, чем было сыграно игр.

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

Авторский коллектив

Четыре автора должны написать книгу из 17 глав, причем первый и третий должны написать по 5 глав, второй — 4, а четвертый — 3 главы книги. Сколькими способами можно распределить главы между авторами?

Указание

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

Решение

Первый автор должен написать 5 глав, причем не важно каких. В каком порядке он это сделал значения не имеет. Значит мы ищем сочетания из 17 глав по 5 главам, который напишет первый автор. Количество этих сочетаний по формуле равно C175C_{17}^5.

Вне зависимости от глав, которые выбрал первый автор, второй выбирает свои 4 главы из 12 оставшихся. Сделать это он может C124C_{12}^4 способами. И так далее по всем авторам.

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

C175C124C85C33=171 531 360C_{17}^5 C_{12}^4 C_{8}^5 C_{3}^3 = 171 \ 531 \ 360
Ответ
C175C124C85C33=171 531 360C_{17}^5 C_{12}^4 C_{8}^5 C_{3}^3 = 171 \ 531 \ 360

Параллельные треугольники

На первой из двух праллельных прямых лежит 10 точек, на второй — 20. Сколько существует треугольников с вершинами в этих точках?

Указание

Разделите все треугольники на две группы: треугольники с двумя вершинами на первой прямой и треугольники с двумя вершинами на второй прямой.

Решение

Первую прямую обозначим буквой a, а вторую b. Выделим два класса треугольников: TaT_a и TbT_b. В классе TaT_a будут треугольники, две вершины которых лежат на прямой a, а третья на b. В классе TbT_b треугольники, две вершины которых лежат на второй прямой b, а третья на a.

Треугольников, которые лежат сразу в обоих классах, не существует (это потребовало бы 4 вершины, а у треугольников их всего 3). Поэтому классы TaT_a и TbT_b не пересекаются.

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

C102=10!(102)! 2!=45C_{10}^2 = \frac{10!}{(10-2)! \ 2!} = 45

В качестве третьей вершины можно выбрать любую из 20 точек на прямой b. Находим количество всех треугольников в TaT_a по правилу умножения:

C10220=4520=900(T1)C_{10}^2 \cdot 20 = 45 \cdot 20 = 900 \quad (T_1)

По такой же логике находим количество треугольников в классе TbT_b:

C20210=19010=1900(T2)C_{20}^2 \cdot 10 = 190 \cdot 10 = 1900 \quad (T_2)

Так как классы TaT_a и TbT_b не пересекаются, то по правилу суммы находим количество всех треугольников, которые можно построить на точках прямых a и b:

900+1900=2800900 + 1900 = 2800
Ответ

2800

Без прекрасного пола никуда

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

Указание

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

Решение

Порядок людей в команде из 6 человек не важен, поэтому каждую такую команду можно рассматривать сочетание. Для подсчета сочетаний будем использовать соответствующую формулу.

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

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

Для групп с двумя женщинами этих самых женщин можно выбрать C42C_4^2 способами. Вне зависимости от сделанного выбора, 4-х мужчин можно выбрать C74C_7^4 способами. По правилу умножения находим все способы собрать команды с двумя женщинами:

C42C74C_4^2 C_7^4

По точно такой же логике находим способы собрать команды с тремя и четырьмя женщинами:

C43C73C44C72C_4^3 C_7^3 \qquad C_4^4 C_7^2

Используем правило суммы и находим общее количество способов собрать группы из 6 человек, в которых не меньше двух женщин:

C42C74+C43C73+C44C72C_4^2 C_7^4 + C_4^3 C_7^3 + C_4^4 C_7^2

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

Найдем все возможные варианты собрать команду из 6 человек без каких-либо дополнительных условий. Для этого находим количество сочетаний из 11 человек по 6 местам в команде: C116C_{11}^6.

Вычтем из общего количества вариантов команды без женщин вообще (C76C_7^6) и только с одной женщиной (C41C75C_4^1 C_7^5) и тогда останутся только команды с двумя и более женщинами:

C116C76C41C75C_{11}^6 - C_7^6 - C_4^1 C_7^5
Ответ
C42C74+C43C73+C44C72илиC116C76C41C75C_4^2 C_7^4 + C_4^3 C_7^3 + C_4^4 C_7^2 \quad или \quad C_{11}^6 - C_7^6 - C_4^1 C_7^5

Туз в рукаве

Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт есть хотя бы один туз? Ровно один туз? Не менее двух тузов? Ровно два туза?

Указание

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

Решение

Есть всего C5210C_{52}^{10} вариантов выбрать 10 карт и C4810C_{48}^{10} способов выбрать 10 карт без тузов (их всего 4). Если мы вычтем из всех способов варианты без тузов вообще, то останутся только варианты, где хотя бы один туз есть:

C5210C4810C_{52}^{10} - C_{48}^{10}

Выбрать один туз можно 4-мя способами (C41C_4^1). Вне зависимости от выбранного туза, есть C489C_{48}^9 способов вынуть остальные 9 карт. Используем правило умножения и получаем все варианты выбрать 10 карт ровно с одним тузом:

C41C489C_4^1 C_{48}^9

Варианты с не менее двумя тузами это варианты с не менее одним тузом, за вычетом вариантов, когда туз ровно один:

C5210C4810C41C489C_{52}^{10} - C_{48}^{10} - C_4^1 C_{48}^9

Выбрать два туза можно C42C_4^2 способами. Вне зависимости от выбранных двух тузов, есть C488C_{48}^8 способов вынуть остальные 8 карт. Используем правило умножения и получаем все варианты выбрать 10 карт с ровно двумя тузами:

C42C488C_4^2 C_{48}^8
Ответ

Хотя бы один туз:

C5210C4810C_{52}^{10} - C_{48}^{10}

Ровно один туз:

C41C489C_4^1 C_{48}^9

Хотя бы два туза:

C5210C4810C41C489C_{52}^{10} - C_{48}^{10} - C_4^1 C_{48}^9

Ровно два туза:

C42C488C_4^2 C_{48}^8

Туз в рукаве

Аналог 1

Настя искала все способы вынуть 10 карт с как минимум одним тузом следующим образом. Вариантов вынуть один туз равно C41C_4^1 и еще C519C_{51}^9 способов как-нибудь вынуть остальные 9 карт. Использовав правило умножения, она получила ответ:

C41C519C_4^1 C_{51}^9

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

Указание

Проблема заключается в множителе C519C_{51}^9, а конкретно в том, что в его вариантах есть тузы.

Решение

Настя не учла возможные дубликаты комбинаций, которые могут возникнуть при таком решении. Проблема кроется в множителе C519C_{51}^9, среди вариантов которого тоже могут встретиться тузы. Из-за чего в ее решении окажутся, например, вот такие два одинаковых варианта (T — туз):

T1 T2 9 картиT2 T1 9 карт T_1 \ \underbrace{T_2 \ \ldots}_{9 \ карт} \qquad и \qquad T_2 \ \underbrace{T_1 \ \ldots}_{9 \ карт}

С другой стороны, если множитель C519C_{51}^9 заменить на множитель без тузов C489C_{48}^9, то мы получим варианты ровно с одним тузом и потеряем все варианты, где тузов два и более! Поэтому, единственный способ тут это идти через вычитание.

Обманчиво простые масти

Сколькими способами можно выбрать из полной колоды, содержащей 52 карты, 6 карт так, чтобы среди них были все четыре масти?

Указание

Шесть карт могут распределиться по четырем мастям (без разницы, каким) только двумя способами:

3+1+1+12+2+1+13 + 1 + 1 + 1 \qquad 2 + 2 + 1 + 1
Решение

Шесть карт могут распределиться по четырем мастям (без разницы, каким) только двумя способами:

3+1+1+12+2+1+13 + 1 + 1 + 1 \qquad 2 + 2 + 1 + 1

Разберем первое распределение. В нем у нас 3 карты одной масти. Всего в каждой масти по 13 карт, поэтому выбрать 3 из них можно C133C_{13}^3 способами. Но и саму масть можно выбрать 4 способами, поэтому общее количество способов увеличивается до 4C1334\cdot C_{13}^3.

Каждую из оставшися трех карт разных мастей можно выбрать 13 способами, то есть всего 131313=13313\cdot13\cdot13 = 13^3 вариантов. Объединяем этот результат с предыдущим и по правилу умножения получаем количество всех вариантов:

4C1331334\cdot C_{13}^3 \cdot 13^3

Теперь второе распределение. В нем по две карты двух мастей. Есть C42C_{4}^2 способа определить эти две масти. В любой из этих мастей далее C132C_{13}^2 способов взять две карты. Всего C42C132C_4^2 C_{13}^2 способов. Ну и 13213^2 вариантов выбрать последние две карты. По правилу умножения получаем количество всех вариантов:

C42C132C132132=C42(C132)2132C_4^2 C_{13}^2 C_{13}^2 \cdot 13^2 = C_4^2 \cdot \left(C_{13}^2\right)^2\cdot 13^2

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

4C133133+C42(C132)21324\cdot C_{13}^3 \cdot 13^3 + C_4^2 \cdot \left(C_{13}^2\right)^2 \cdot 13^2
Ответ
4C133133+C42(C132)21324\cdot C_{13}^3 \cdot 13^3 + C_4^2 \cdot \left(C_{13}^2\right)^2 \cdot 13^2

Кубоидный мир победил

Сколько можно построить различных прямоугольных параллелепипедов (кубоидов), у которых длина каждого ребра является целым числом от 1 до 10?

Указание

Любой кубоид задается длиной, шириной и высотой.

Решение

Кубоид задается набором из 3 чисел: длины, ширины и высоты. Каждое его ребро будет равно одной из этих трех величин.

Выходит, задача сводится к нахождению количества способов выбрать три величины кубоида из чисел от 1 до 10. Конкретные «названия» величин (длина, ширина и высота) условные и влияния на форму кубоида не влияют.

Например, кубоид с длиной и шириной в 1, а высотой в 3 можно «опрокинуть на бок» и совместить с кубоидом с длиной и высотой в 1, а шириной в 3, а значит это один и тот же кубоид.

Поэтому, мы ищем сочетания с повторениями из 10 доступных размеров по 3 величинам кубоида. Найдем количество таких сочетаний по формуле:

Cˉ103=C10+313=12!9! 3!=220\bar{C}_{10}^3 = C_{10+3-1}^3 = \frac{12!}{9! \ 3!} = 220
Ответ

Cˉ103=220\bar{C}_{10}^3 = 220

Одинаковые кости судьбы

Сколькими способами могут выпасть три одинаковые игральные кости? Во скольких случаях хотя бы на одной кости выпадет 6 очков? Во скольких случаях ровно на одной кости выпадет 6 очков? Во скольких случаях ровно на одной кости выпадет 6 очков, а на другой — 3 очка?

Указание

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

Решение

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

Каждая из 3 костей может упасть на одну из 6 сторон. Каждый способ выпадания трех костей можно представить как сочетание с повторениями из 6 возможных выпавших сторон по 3 костям. Находим количество этих сочетаний по формуле:

Cˉ63=C6+313=8!5! 3!=56\bar{C}_6^3 = C_{6+3-1}^3 = \frac{8!}{5! \ 3!} = 56

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

Cˉ63Cˉ53=5635=21\bar{C}_6^3 - \bar{C}_5^3 = 56 - 35 = 21

Для выпадения ровно одной шестерки сначала 3-мя способами выбираем кость, на которой выпадет шестерка. Вне зависимости от выбранной кости оставшиеся две могут выпасть Сˉ52\bar{С}_5^2 способами. Используем правило умножения:

3Cˉ52=453\cdot \bar{C}_5^2 = 45

Для выпадения ровно одной шестерки и тройки сначала выберем пару костей, на которых выпадет 6 и 3: C32C_3^2. Вне зависимости выбора двух костей, на оставшейся третьей кости может выпасть 4 возможных стороны. Используем правило умножения:

C324=12C_3^2 \cdot 4 = 12
Ответ

Варианты выпадения трех костей:

Cˉ63=C6+313=8!5! 3!=56\bar{C}_6^3 = C_{6+3-1}^3 = \frac{8!}{5! \ 3!} = 56

Если есть хотя бы одна кость с 6 очками:

Cˉ63Cˉ53=5635=21\bar{C}_6^3 - \bar{C}_5^3 = 56 - 35 = 21

Если есть ровно одна кость с 6 очками:

3Cˉ52=453\cdot \bar{C}_5^2 = 45

Если на одной кости ровно 6 очков, а на другой 2:

C324=12C_3^2 \cdot 4 = 12

Анализ уравнений

Красивая

Сколько решений в неотрицательных целых числах имеет следующее уравнение?

x+y+z+q=10x + y + z + q = 10
Указание

Расположите единицы в ряд и назначайте им переменные.

Решение

Раз справа стоит 10, то и слева мы должны получить 10. Использовать мы можем только натуральные числа и 0. Каждое из этих чисел можно представить как набор единиц: 3 — это три единицы, 0 — ноль единиц. В сумме должно получиться 10 единиц.

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

1x, 1x, 1z, 1q, 1x, 1x, 1z, 1z, 1x, 1x\overset{\small x}{1}, \ \overset{\small x}{1}, \ \overset{\small z}{1}, \ \overset{\small q}{1}, \ \overset{\small x}{1}, \ \overset{\small x}{1}, \ \overset{\small z}{1}, \ \overset{\small z}{1}, \ \overset{\small x}{1}, \ \overset{\small x}{1}

Эта комбинация обозначает решение уравнение со следующими значениями переменных:

x=6,y=0,z=3,q=1x=6, \quad y =0, \quad z = 3, \quad q = 1

Каждое распределение переменных по единицам можно рассматривать как сочетание с повторениями из 4 переменных по 10 единицам. Найдем количество таких сочетаний по формуле:

Cˉ410=C4+10110=(4+101)!(41)! 10!=1112136=286\bar{C}_4^{10} = C_{4+10-1}^{10} = \frac{(4+10-1)!}{(4-1)! \ 10!} = \frac{11 \cdot 12 \cdot 13}{6} = 286

Итак, уравнение имеет 286 решений в неотрицательных числах.

Ответ

Cˉ410=286\bar{C}_4^{10} = 286

Анализ уравнений

Аналог 1

Сколько решений в неотрицательных целых числах имеет следующее уравнение?

{{{ equation }}}

Ответ

{{{ answer }}}

Нули тоже хотят любви!

Красивая

Сколькими способами число n можно разложить на m слагаемых при условии, что ноль тоже считается за отдельное слагаемое?
Порядок слагаемых имеет значение!

Указание

Адаптируйте решение задачи «Анализ уравнений» или используйте метод перегородок.

Решение

Распишем число n в виде n единиц. Каждой единице назначаем свое слагаемое:

n=1С1, 1С4, 1Сm, 1Сm, n = \overset{\small С_1}{1},\ \overset{\small С_4}{1},\ \overset{\small С_m}{1},\ \overset{\small С_m}{1},\ \ldots

Если какому-то слагаемому или слагаемым не досталась единица, то считаем, что они равны нулю.

Каждое распределение слагаемых по единицам можно рассматривать как сочетание с повторениями из m слагаемых по n единицам. Найдем количество таких сочетаний по формуле:

Cˉmn=Cn+m1n=(n+m1)!n! (m1)!\bar{C}_m^n = C_{n+m-1}^n = \frac{(n+m-1)!}{n! \ (m-1)!}

Через перегородки

Задачу можно решить и методом перегородок. Распишем число n в виде n единиц:

n=1111nn = \underbrace{1111\ldots}_{n}

Между этими единицами или по бокам от них можно расставить m1m-1 «разделителей» слагаемых — перегородок (|). Если по какую-то сторону от перегородки нет единицы, то будем считать, что там стоит ноль. Примеры:

111=2+1+0111=0+0+2+0+1111=0+0+0+311|1| = 2 + 1 + 0 \\ ||11||1 = 0 + 0 + 2 + 0 + 1 \\ |||111 = 0 + 0 + 0 + 3

Тогда количество способов число n разложить m слагаемых, включая нули, равно количеству перестановок с повторениями из n единиц и m1m-1 перегородок:

P(n, m1)=(n+m1)!n! (m1)!P(n, \ m-1) = \frac{(n + m - 1)!}{n! \ (m-1)!}
Ответ
Cˉmn=Cn+m1n=(n+m1)!n! (m1)!\bar{C}_m^n = C_{n+m-1}^n = \frac{(n+m-1)!}{n! \ (m-1)!}
Примечание

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

Математический интерес

Выписаны все сочетания с повторениями из n букв по n. Покажите, что каждая буква встретится C2n1nC_{2n-1}^n раз.

Указание

Покажите, что все буквы встречаются среди сочетаний одинаковое количество раз. Используйте этот факт для решения задачи.

Решение

В условии говорится, что были выписаны все сочетания с повторениями. Найдем их поличество по формуле:

Cˉnn=Cn+n1n=C2n1n\bar{C}_n^n = C_{n+n-1}^n = C_{2n-1}^n

Имеем C2n1nC_{2n-1}^n сочетаний, каждое из которых состоит из n букв. То есть всего в этих сочетаниях nC2n1nn C_{2n-1}^n букв. Так как каждая буква встречается среди этих сочетаний одинаковое количество раз, то делим это выражение на количество букв (n) и получаем количество раз, которое встретится каждая буква:

nC2n1nn=C2n1n\frac{n C_{2n-1}^n}{n} = C_{2n-1}^n

\blacksquare

А там армяне в нарды играют

Сложная

В восточной игре «нарды» 15 белых и 15 черных шашек стоят на 24 полях так, что каждое поле или пустое, или занято несколькими белыми шашками, или занято несколькими черными шашками. Сколькими способами можно расставить шашки на полях по этим правилам?

Указание

Обозначьте буквой p количество полей, на которые будут поставлены белые фишки. p находится в границах от 1 до 15. На основе этой буквы постройте количество вариантов расставить фишки на доске.

Решение

Обозначим буквой p количество полей, на которые будут поставлены белые фишки. p находится в границах от 1 до 15:

1p151 \leq p \leq 15

С количеством полей для белых фишек разобрались. Теперь нужно по факту выбрать из 24 доступных полей те самые p полей. Находим количество способов это сделать по формуле сочетаний из 24 по p:

C24pC_{24}^p

Раз это белые поля, то на них должна быть как минимум одна белая фишка (иначе они будут пустыми). Поэтому сразу расставляем p белых фишек, по одной на каждое «белое» поле.

Оставшиеся 15p15 - p белых фишек можно расставить по p полям любым образом. Количество способов это сделать можно найти по формуле сочетаний с повторениями, распределяя p позиций по 15p15-p оставшимся белыми фишкам: Cˉp15p\bar{C}_p^{15-p}.

Выбор «белых» полей (C24pC_{24}^p) никак не влияет на количество способов расставить по ним фишки (Cˉp15p\bar{C}_p^{15-p}), поэтому мы можем использовать правило произведения и найти количество вариантов сделать оба этих действия:

C24pCˉp15pC_{24}^p \bar{C}_p^{15-p}

Осталось только распределить оставшиеся 24p24-p полей по 15 черным фишкам. Сделать это можно Cˉ24p15\bar{C}_{24-p}^{15} способами, причем вне зависимости от предыдущих действий. Поэтому и здесь применяем правило умножения:

C24pCˉp15pCˉ24p15C_{24}^p \bar{C}_p^{15-p} \bar{C}_{24-p}^{15}

Вспоминаем, что p у нас принимает все значения от 1 до 15. Получается 15 групп с уникальными расстановками фишек. Значит, для нахождения количества вообще всех вариантов можно использовать правило суммы:

C241Cˉ1151Cˉ24115+C242Cˉ2152Cˉ24215++C2415Cˉ151515Cˉ241515 C_{24}^1 \bar{C}_1^{15-1} \bar{C}_{24-1}^{15} + C_{24}^2 \bar{C}_2^{15-2} \bar{C}_{24-2}^{15} + \ldots + C_{24}^{15} \bar{C}_{15}^{15-15} \bar{C}_{24-15}^{15}

Запишем это выражение короче, используя символ суммы:

p=115C24pCˉp15pCˉ24p15\sum\limits_{p = 1}^{15} C_{24}^p \bar{C}_p^{15-p} \bar{C}_{24-p}^{15}
Ответ
p=115C24pCˉp15pCˉ24p15\sum\limits_{p = 1}^{15} C_{24}^p \bar{C}_p^{15-p} \bar{C}_{24-p}^{15}
Правки и новые задачи
  • Комбинаторная алгебра — уравнения и неравенства с сочетаниями. Например из Math Excercises

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

  • Часть задач с другими лотереями вынести в практикум.

  • Пример с комбинацией элементов из игры Magica, причем некоторые два элемента объединяются вместе и образуют новый элемент!

Превью