Сколькими способами медали могут быть распределены между командами

(a 1 , b 1 ), (a 1 , b 2 ), …, (a 1 , b k ),

(a 2 , b 1 ), (a 2 , b 2 ), …, (a 2 , b k ),

(a m , b 1 ), (a m , b 2 ), …, (a m , b k ).

Общее число N всевозможных пар равно m  k, т. е. N=n(A)  n(B).

Таким образом, справедлива теорема 2.

Теорема 2. Если множества А и В конечны, то число N всевозможных пар

(а, Ь), а  А, b  B равно произведению чисел элементов этих множеств:

С помощью метода математической индукции теорема 2 обобщается на любое конечное число множеств.

Следствие 2. Если имеется k конечных множеств A 1 , A 2 , . A K то число N всевозможных наборов (a 1 , a 2 , …, a k ), где a 1  A 1 , a 2  A 2 , …, a k  A k , равно

N=n(A 1 )  n(A 2 )  .  n(A k ).

Пример 3 . Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Решение. Цифра разряда десятков тысяч и цифра разряда единиц должны быть одинаковыми, не равными 0 (9 возможностей); цифра разряда тысяч и разряда десятков может быть любой (10 возможностей); цифра разряда сотен может быть любой (10 возможностей). Итак, согласно правилу произведения, всего искомых чисел 9  10  10=900.

Пример 4. Сколько существует шестизначных чисел, которые делятся на пять?

Решение. Поскольку число делится на 5, то его цифра разряда единиц равна 0 или 5

(2 возможности). Цифры разряда десятков, сотен, тысяч и десятков тысяч могут быть любыми ( то есть в каждом из этих случаев имеется 10 возможностей). Цифра разряда сотен тысяч шестизначного числа может быть любой, кроме 0 (9 возможностей). Следовательно, всего искомых чисел 9  10  10  10  10  2=180000.

Пример 5. В розыгрыше первенства по футболу принимают участие 18 команд. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали, если любая команда может получить только одну медаль?

Решение . Одну из медалей, например бронзовую, может получить одна из 18 команд (18 возможностей). После того как определился бронзовый призер, обладателем другой медали, н а пример золотой, может стать одна из оставшихся 17 команд (17 возможностей). После того как определились бронзовый и з о лотой призеры, обладателем серебряной медали может быть одна. из оставшихся. 16 команд (16 возможностей). Следовательно, общее число способов, которыми могут быть распределены золотая, серебряная и бронзовая медали, равно 18  17  16==4896.

Пример 6. В столовой предлагают два различных первых блюда a 1 и а 2 , три различных вторых блюда b 1 , b 2 , b 3 и два вида десерта с 1 и c 2 . Сколько различных обедов из трех блюд может предложить столовая?

Решение. Обозначим множество первых блюд через A, множество вторых — через В и множество третьих — через С. По условию

Каждый обед определяется набором из трех блюд (а, Ь, с), где а  A, b  B, с  С. По правилу произведения

столовая может предложить 12 различных обедов. Графическая иллюстрация этого решения приведена на рисунке 2:

Второе Десерт ОБЕД

Начало (a 1, b 3 , c 2 )

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

В комбинаторике рассматривают три типа комбинаций об ъ ектов: размещения, перестановки и сочетания. Рассмотрим их.

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

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

1. Комбинации, отличающиеся друг от друга составом элеме н тов или их порядком, каждая из которых содержит k (k  n) элементов, взятых из n различных элементов, называются разм е щениями из п элементов по k.

Например, выпишем все размещения из элементов а, Ь, с, d по два:

ab, Ьа, ас, са, ad, da, be, cb, bd, db, cd, dc.

2. Комбинации, каждая из которых содержит п различных элементов, взятых в определенном порядке, называются перест а новками из п элементов .

Например, выпишем все перестановки из элементов а, Ь, с:

аЬс, acb, Ьас, Ьса, cab, cba.

3. Комбинации, отличающиеся друг от друга по крайней мере, одним элементом, каждая из которых содержит k элементов, взятых из п различных элементов, называются сочетаниями (выборками) из п элементов по k. Порядок следования элементов не учитывается.

Например, выпишем все сочетания из элементов а, Ь, с, d, е по три:

аЬс, abd, abe, acd, асе, ade, bed, bee, bde,cde.

1. Размещения без повторений

При решении различных задач возникает вопрос о том, сколькими способами можно выбрать k объектов из множества, содержащего п таких объектов, причем k объектов должны в ы бираться в определенном порядке. Другими словами, сколькими способами можно выбрать и разместить по k различным местам k из n различных предметов?

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

Решение. Это задача о выборе и размещении по семи различным местам семи из десяти различных цифр. Существует 10 способов выбора первой цифры телефонного номера. Так как, по условию, цифры в номере не могут повторяться, то после того, как выбрана первая цифра номера, остаётся 9 способов выбора второй цифры номера. После выбора первой и второй цифр номера остаётся 8 способов выбора третьей цифры номера и так далее. И, наконец, после выбора первых шести цифр номера остаётся четыре способа выбора последней седьмой цифры семизначного номера; поэтому, согласно правилу произведения, число указанных телефонных номеров равно 10  9  8  7  6  5  4=604800

Определение. Размещениями из n объектов по k назыв а ют любой выбор k объектов, взятых в определенном порядке из n объектов. Число размещений из п объектов по k об о значают A k n .

Формула для числа A k n получается обобщением результата, полученного в примере 4.

Действительно, существует п способов выбора первого объе к та. После того как он выбран, остается (п- 1) способ для выб о ра второго объекта. После выбора первого и второго объектов остается (п- 2) способа для выбора третьего объекта, и вообще после выбора объектов от первого до (k-l)-гo остается (п-k +1) способ для выбора k-го объекта. По правилу произведения имеем:

Формула (1) и дает решение поставленной вначале задачи: в ы брать и разместить по k различным местам k из п различных пре д метов можно

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

Решение. Искомые команды будут отличаться между с о бой или учащимися, или их

порядком, который указывает, на к а кую олимпиаду пойдет ученик. Поэтому искомое число равно числу размещений из 30 по 4 и по формуле (1) получаем:

Это значит, что существует 657 720 способов выбора команды.

Преобразуем формулу (1) для числа размещений.

Вначале для удобства дальнейшей записи введем специальный символ.

Определение. Произведение всех натуральных чисел от 1 до n обозначается n! и читается «эн факториал». Таким образом

n!=1  2  3  …  (n-1)  n.

1!=1; 2!=1  2=2; 3!=1  2  3=6; 4!=1  2  3  4=24; 5!=1  2  3  4  5=120; 6!=1  2  3  4  5  6=720.

Вычислять n! для больших значений n крайне трудно, ибо с увеличением n величина n! растет очень быстро.

Для удобства условились считать, что 0!=1.

Теперь вернемся к преобразованию формулы (1). Умножим и разделим правую часть формулы (1) на произведение чисел 1  2  3  …  (n-k) и получим другую формулу для вычисления:

1. Перестановки без повторений

Если в размещениях рассмотреть случай k=n, то мы получим размещения, отличающиеся друг от друга только порядком элементов. Другими словами, возникает вопрос: сколькими способами можно переставить n различных предметов, расположенных на n различных местах?

Определение. Размещения из n элементов по n называются перестановками.

Число перестановок обозначается P n . Из формулы (1) для вычисления числа P n получаем:

Пример 9. Сколько всего шестизначных четных чисел можно составить из цифр 1, 3, 4, 5, 7 и 9, если из этих чисел ни одна не повторяется.

Решение. Необходимым и достаточным условием делимости натурального числа на 2 является делимость на 2 цифры разряда единиц этого числа. Поэтому из всех указанных цифр цифрой единиц искомого числа может быть только цифра 4. Остальные пять цифр могут стоять на оставшихся пяти местах в любом порядке. Следовательно, поставленная задача сводится к нахождению числа перестановок из 5 элементов. Поскольку P 5 =5!=1  2  3  4  5=120, то всего можно составить 120 указанных чисел.

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

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

P 8 =8!=1  2  3  4  5  6  7  8=40320, то выполнить условия задачи можно 40320 способами.

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

Решение. Ясно, что в этом случае на каждой горизонтали и каждой вертикали шахматной доски может быть расположено только по одной ладье, в противном случае они могут взять друг друга. Число возможных позиций – число перестановок из 8 элементов: P 8 =8!=40320.

1. Сочетания без повторений

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

Определение. Сочетаниями из n объектов по k называют любой выбор k объектов, взятых из n объектов.

Из определения сочетаний следует, что они отличаются друг от друга только элементами. Число сочетаний из n объектов по k обозначают C k n . Выясним сколькими способами можно выбрать m из n различных предметов.

Выбрать k из n разных предметов можно C k n способами, и в каждом из выбранных сочетаний имеется k! возможностей упорядочить k предметов этого сочетания. Поэтому, согласно правилу произведения, имеется k!  C k n возможностей выбрать и разместить по k разным местам k из n разных предметов, то есть

Откуда следует, что число сочетаний из n разных предметов по k в k! раз меньше числа размещений из n по k, то есть

Если для вычисления A k n использовать формулу (2), то получим еще одну формулу для вычисления C k n :

Заменим в формуле (4) число k на число n-k. Тогда

Отсюда следует, что

Равенство (5) совершенно очевидно: каждой выборке, содержащей k элементов из имеющихся n, соответствует выборка из (n-k) оставшихся элементов.

Пример 12. В классе 25 учеников. Сколькими способами из них можно выбрать четырех учащихся для дежурства на вечере?

Решение. Искомое число совпадает с C 4 25 и по формуле (4) равно:

Пример 13. У 6 взрослых и 11 детей обнаружены признаки инфекционного заболевания. Чтобы проверить заболевание, следует взять выборочный анализ у 2 взрослых и 3 детей. Сколькими способами можно это сделать?

Решение. Из 6 взрослых выбрать двух можно

Из 11 детей выбрать трех можно

Согласно правилу произведения имеется15  165=2475 способов выбора двух взрослых и трех детей.

Пример 14 . Доказать, что

Решение . Пусть даны n элементов  1 ,  2 ,  3 ,… ,  n . Будем различать эти элементы по их индексам.

Число всех сочетаний по k элементов, содержащих элемент  k и не содержащих элементов с

большим индексом, можно образовать C k-1 k-1 способами.

Число всех сочетаний по k элементов, содержащих элемент  k+1 и не содержащих элементов с большим индексом, можно образовать C k-1 k способами.

Число всех сочетаний по k элементов, содержащих элементы  k+2 и не содержащих элементов с большим индексом, можно образовать C k-1 k+1 способами. И так далее. Наконец, число всех сочетаний по k элементов, содержащих элемент  n , можно образовать C k-1 n-1 способами. Согласно правилу сложения, число сочетаний из элементов  1 ,  2 ,  3 ,… ,  n по k элементов равно

В то же время число сочетаний из n элементов по k равно C k n . Таким образом, имеем

Пример 15 . Из двух математиков и десяти экономистов надо составить комиссию в составе восьми человек. Сколькими способами может быть составлена комиссия, если в нее должен входить хотя бы один математик?

Решение . В указанной комиссии может быть либо один математик и семь экономистов, либо два математика и шесть эк о номистов.

Выбор одного математика из двух возможен С 1 2 =2/1 =2 способами, а семи экономистов из десяти – С 7 10 =С 3 10 =120 способами. По правилу произведения число способов выбора к о миссии из одного математика и семи экономистов равно С 1 2 С 7 10 =2  120=240.

Выбор двух математиков из двух возможен С 2 2 =(1  2)/(1  2)=1 способом, а выбор шести экономистов из десяти возможен C 6 10 =С 4 10 =210 способами. По правилу произведения число способов выбрать комиссию из двух математиков и шести экономистов ровно С 2 2 С 6 10 = =1  210=210. Общее число способов выбора комиссии с одним математиком или комиссии с двумя математиками по правилу суммы равно

Указанная комиссия может быть выбрана 450 способами.

Приведем другой способ решения этой задачи. Всего комиссий по восемь человек из 12 человек можно составить

способами. Эти комиссии можно разбить на два типа:

а) к одному типу относится комиссия, состоящая только из экономистов;

б) к другому типу относится комиссия, в которую входит хотя бы один математик.

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

то число способов составить комиссию в составе восьми человек, в которую входит хотя бы один математик, равно 495—45=450.

Пример 16 . Сколько существует делителей числа 210?

Решение . Разложим данное число на простые множители: 210=2  3  5  7. Число делителей, составленных из произведения двух простых множителей, равно C 2 4 =2  3=6 (а именно числа

6, 10, 14, 15, 21, 35); число делителей, составленных из произв е дения трех простых множителей, равно С 3 4 =4 (а именно числа. 30, 42, 70, 105); число простых делителей равно четырем (а именно числа 2, 3, 5, 7). Кроме того, делителями являются число 1 и число 210.

Итак, согласно правилу сложения, число всех делителей равно 6+4+4+1+1=16.

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

Решение . Пусть М, N и Р — пассажиры, которым безра з лично, где сидеть. Если М сядет лицом в направлении движения поезда, то на диване вместе с ним еще три указанных пассажира могут сесть 4! способами (число перестановок из 4). Остальные пассажиры на противоположном диване также могут разместиться 4! способами. Таким образом, если М выбрал место лицом в напра в лении движения поезда, то для каждой из 4! возможностей ра з меститься на одном диване имеется 4! возможности разместиться на другом диване; поэтому, согласно правилу умножения, в этом случае все пассажиры могут разместиться 4!4!=24  24==576 сп о собами.

Такое же число способов получится, если лицом в направл е нии движения поезда сядет пассажир N или пассажир Р.

Поэтому, согласно правилу сложения, число всевозможных способов разместиться пассажирам в купе с учетом их пожеланий и порядка размещения на каждом диване равно (4!) 2 +(4!) 2 +(4!) 2 =3  576=1728.

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

1. Размещения с повторениями

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

Каким минимальным признаком может отличаться одна такая комбинация объема k от другой комбинации такого же объема? Это равносильно вопросу: каким минимальным признаком могут отличаться узоры лент, построенных из одинакового количества квадратов?

Иной окраской по крайней мере одного квадрата (в приводимом ниже примере k=8, n=5)

порядком расположения квадратов в линейном строю

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

их различие по крайней мере одним элементом или их различие порядком расположения элементов. Как видно, эти признаки совпадают с признаками, о которых шла речь в пункте 1, поэтому комбинации о которых идет речь сейчас, следует называть размещениями с повторениями из n элементов по k.

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

Например, числа 33, 44, 55, 34, 43, 35, 53, 45, 54 являются размещениями по два из трех элементов с повторениями (в данном примере k=2, n=3).

Замечание. Размещения с повторениями можно рассматривать и в случае k>n, то есть неравенство n  k, которое считалось необходимым в пункте 1, здесь необходимым уже не является.

Например, из n=2 элементов a, b можно образовать размещения с повторениями по k=3 элемента. Они будут иметь вид:

Задача о числе размещений с повторениями. Сколькими способами можно разместить по k различным местам любые k предметов, выбранных из n различных предметов с повторениями каждого из них любое число раз, но не более k? Количество всех таких способов обозначим A k n (П) (читается «число размещений из «эн» по «ка» с повторениями»).

Пример 18 . Каждый телефонный номер состоит из семи цифр. Сколько всего телефонных номеров, не содержащих других цифр, кроме 2, 3, 5 и 7?

Решение . Это задача о числе размещений в семи разных местах семи цифр, выбранных из четырех разных цифр с повторениями каждой из них любое число раз, но не более семи. Существует 4 способа выбора первой цифры телефонного номера. Так как, по условию цифры номера могут повторяться, то существует по 4 способа выбора второй, третьей, четвертой и так далее седьмой цифр номера, поэтому, согласно правилу произведения, число всех указанных телефонных номеров равно 4  4  4  4  4  4  4= 4 7 = 16384

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

Утверждение. Для каждого фиксированного натурального числа n и любого натурального числа k справедливо равенство

то есть число всевозможных размещений из n по k с повторениями равно n k .

Доказательство. Доказательство утверждения проведем методом математической индукции по k.

Пусть k=1. На одно место можно поместить любой из n различных предметов, каждый из которых в этом случае может повторяться не более одного раза; поэтому имеется n возможностей, то есть A 1 n (П)=n=n 1 .

Для k=1 утверждение верно.

Предположим, что для k=m справедливо равенство

Пусть k=m+1. По предположению имеется n m возможностей разместить по m различным местам любые m предметов, выбранных из п различных предметов с повторением каждого из них любое число раз, но не более m. Для каждой такой возможности на (m+1)-е оставшееся место можно, учитывая, что каждый из п предметов повторяется любое число раз, но не более m+1 раз, поместить любой из предметов, т. е. имеется п возможностей. Согласно правилу умножения, разместить по m+1 различным местам m+1 предметов, выбранных из п различных предметов с повторением каждого из них любое число раз, но не более m+1 раз, можно п m  п способами, т. е. и для k=m+1 справедливо равенство

Итак, для k =1 утверждение верно, а из предположения о справедливости его для k= m следует, что оно верно и для k=m+1. Тем самым доказано, что равенство

верно для любого натурального k при каждом фиксированном п.

По определению положим A 0 n (П)=1.

Пример 19 . Буквы азбуки Морзе состоят из символов – точка и тире. Сколько букв получим, если потребуется, чтобы каждая буква состояла не более чем из пяти указанных символов?

Решение . Число всех букв, каждая из которых записывается одним символом, равно А 1 2 (П)=2 1 =2.

Число всех букв, каждая из которых записывается двумя символами, равно А 2 2 (П)=2 2 =4.

Число всех букв, каждая из которых записывается тремя символами, равно А 3 2 (П)=2 3 =8.

Число всех букв, каждая из которых записывается четырьмя символами, равно А 4 2 (П)=2 4 =16.

Число всех букв, каждая из которых записывается пятью символами, равно А 5 2 (П)=2 5 =32.

Число всех указанных букв равно 62.

Пример 20 . Сколькими способами можно разместить восемь пассажиров в три вагона?

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

То 8 пассажиров можно разместить в 3 вагона 6561 различным способом.

1. Перестановки с повторениями

При перестановке букв в слове «толпа» получается P 5 =5!=120 «слов». Если же переставлять буквы в слове «топот», то получится меньше различных «слов» потому, что ни перестановка двух букв «т», ни перестановка двух букв «о» не изменяют «слова». Мы имеем здесь дело с перестановками с повторениями.

Определение. Комбинации из n предметов, в каждую из которых входят n 1 одинаковых предметов одного типа, n 2 одинаковых предметов другого типа и так далее до n k одинаковых предметов k-го типа, где n 1 +n 2 +…+n k =n, называются перестановками из n элементов с повторениями.

Например, числа 4455, 5544, 5454, 4545, 4554, 5445 являются перестановками с повторениями цифр 4 и 5, каждая из которых взята по два раза.

При решении различных задач возникает вопрос о том, сколькими способами можно переставить n предметов k различных типов каждого типа соответственно по n 1 , n 2 ,…,n k одинаковых предметов, расположенных на n различных местах?

Число всех таких перестановок с повторениями принято обозначать C n (n 1 , n 2 ,…,n k ), и оно может быть найдено по формуле

Показательство. Возьмем некоторую перестановку из числа P n (n 1 , n 2 ,…,n k ) всех перестановок с повторениями. В ней все возможные перестановки предметов первого типа, считая их разными , можно осуществить n 1 ! способами, затем все возможные перестановки предметов второго типа, считая их разными , можно осуществить n 2 ! способами и так далее, а затем все возможные перестановки предметов k-го типа, считая их разными , можно осуществить n k ! способами. Осуществляя все возможные перестановки только предметов каждого типа, получим n 1 !n 2 !…n k ! перестановок, которые бы возникли из взятой перестановки с повторениями, если бы имелась возможность как-то различать входящие в каждый тип одинаковые предметы. Проделав это для каждой перестановки с повторениями, получим n! – число всевозможных перестановок из n различных предметов.

Таким образом, n 1 !n 2 !…n k !  P n (n 1 , n 2 ,…,n k )=n!, откуда следует формула для числа перестановок с повторениями.

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

Пример 22 . Сколько всего семизначных чисел, у каждого из которых цифра 6 встречается три раза, а цифра 5 – четыре раза?

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

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

Выбрать три этажа из шести и распределить их среди трех разных групп можно

Следовательно, согласно правилу произведения, число всех способов выполнить условия задачи равно

6. Сочетания с повторениями

В заключении рассмотрим так называемые сочетания с повторениями.

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

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

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

Например, из трех элементов a, b, c можно образовать такие сочетания с повторениями по два элемента:

Из тех же трех элементов сочетания с повторениями по три элемента будут следующими:

aaa, aac, abc, acc, bcc,

aab, abb, bbb, bbc, ccc.

Ясно, что из элементов a, b, c можно составлять сочетания с повторениями и по четыре элемента и вообще по любому числу k элементов, так что для сочетаний с повторениями неравенство k  n не является необходимым, а можно рассматривать и случай k>n.

Задача о числе сочетаний с повторениями. Число различных возможных сочетаний с повторениями из n элементов по k принято обозначать C k n (п), и оно может быть найдено по формуле

Показательство. Это вытекает из следующих рассуждений. Обозначим предметы через  1 ,  2 , …,  n ; тогда число всех сочетаний из n предметов по k с повторениями равно C k n (п). Каждое такое сочетание либо содержит, либо не содержит предмет  1. Число сочетаний, которые не содержат  1, равно C k n-1 (п) (это – число сочетаний с повторениями, из предметов  2 ,  3 , …,  n ).

Каждое сочетание, содержащее  1, может быть получено присоединением  1 к некоторому сочетанию из n предметов по k-1 с повторениями, число которых равно C k-1 n (п).

Следовательно, справедливо следующее рекуррентное соотношение:

Поскольку (смотри пример 14)

Рассуждая аналогично, на (k-1)-м шаге получим

Таким образом, если имеется по k одинаковых предметов каждого из n различных типов, то число всех способов выбрать k из этих k  n предметов равно

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

Решение. Это задача о числе сочетаний из двух по четыре с повторениями.

То выбрать монеты указанным в условии задачи образом можно пятью способами.

Пример 25 . Сколько всего чисел можно составить из цифр 1, 2, 3, 4, 5, в каждом из которых цифры расположены в неубывающем порядке?

Решение. Это задача о числе сочетаний из пяти цифр по одному, по два, по три, по четыре и по пяти с повторениями в каждом случае.

То существует 5+15+35+70+126=251 чисел, удовлетворяющих условию задачи.

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

Решение. Число костей домино можно рассматривать как число сочетаний с повторениями по два из десяти. Число таких сочетаний равно

Решение комбинаторных задач.

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

Пример 27. Шесть пассажиров садятся на остановке в тра м вайный поезд, состоящий из трех трамвайных вагонов. Каким числом различных способов могут они распределиться в вагонах?

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

Сначала рассмотрим случай, когда учитывается, кто в каком вагоне находится, то есть когда случаи «пассажир А в первом в а гоне, а пассажир В — во втором» и «пассажир В в первом вагоне, а пассажир А — во втором» считаются различными. В этом случае, данную задачу можно рассматривать, как задачу о числе размещений среди 6 пассажиров любых шести вагонов, взятых из 3 различных вагонов, с повторениями каждого из них любое число раз но не более 6 (количество одинаковых вагонов в размещении указывает на число находящихся в нем пассажиров.

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

(Другой способ: Первый пассажир, может войти в любой из трех вагонов, также как и второй, то есть для двух пассажиров имеется 3 2 возможностей. Аналогично для 6 пассажиров, имеется 3 6 возможностей).

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

C 6 3 (П)=C 6 8 =C 2 8 =28.

Пример 28. Сколькими способами можно распределить 28 костей домино между 4 игроками так, чтобы каждый получил 7 костей?

Решение. Первый игрок может выбрать 7 костей C 7 28 сп о собами. После этого второй игрок должен выбрать 7 костей из оставшихся 21 кости. Это можно сделать C 7 21 способами. Третий игрок может выбрать кости С 7 14 способами, а четвертый — C 7 7 = 1 сп о собом. Всего получаем

способов раздела костей.

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

Пример 29. Сколькими способами можно положить 28 различных открыток в 4 одинаковых конверта так, чтобы в каждом конверте лежало по 7 открыток?

Решение. Сначала пометим конверты цифрами 1, 2, 3, 4. Тогда, согласно примеру 28, число различных раскладок равно 28!/(7!) 4 . После этого сотрем пометки. Теперь конверты можно произвольно переставлять друг с другом, не меняя результата раскладки (ведь они теперь неотличимы друг от друга). Так как число различных перестановок четырех конвертов равно 4!, то число различных раскладок уменьшается в 4! раза, и потому оно равно 28!/(4!  (7!) 4 ).

Пример 30. Сколькими способами можно разделить 40 яблок между 4 мальчиками (все яблоки считаются одинаковыми)?

Решение. Возьмем три одинаковые перегородки и рассм о трим всевозможные перестановки 43 предметов: 40 яблок и 3 пер е городок. Каждой такой перестановке соответствует свой способ раздела: первый мальчик получает все яблоки от начала до первой перегородки, второй — все яблоки между первой и второй перег о родками, третий — все яблоки между второй и третьей пер е городками, а четвертый — все остальные яблоки. (Если, например первая и вторая перегородки оказались рядом, то второй мальчик ничего не получает.) Значит, число способов раздела равно числу

перестановок 40 яблок и 3 перегородок. По формуле числа перест а новок с повторениями получаем, что это число равно

Пример 31. Сколькими способами можно разделить 40 яблок между 4 мальчиками так, чтобы каждый получил по крайней мере 3 яблока (все яблоки по-прежнему считаются одинаковыми)?

Решение. Сначала дадим каждому мальчику по 3 яблока. А потом разделим оставшиеся 28 яблок так, как было сделано в пр е дыдущей задаче. Всего получаем способов раздела.

Пример 32. Имеется т различных сигнальных флагов и k мачт, на которых их вывешивают. Значение сигнала зависит от того, в каком порядке развешаны флаги. Сколько сигналов можно передать этими флагами, если все флаги должны быть использованы, но некоторые из мачт могут оказаться пустыми?

Решение. Добавим к т флагам k- 1 перегородку и ра с смотрим всевозможные перестановки из т различных флагов и k-1 одинаковых перегородок. Как и в примере 30, каждой перестановке соответствует свой сигнал (на первую мачту вывешиваются по п о рядку все флаги от начала до первой перегородки и т. д.). Поэтому число сигналов равно числу таких перестановок, то есть равно

Если бы мы не потребовали, чтобы все флаги были использов а ны, то число сигналов оказалось бы больше. В этом случае задача решалась бы в два этапа. Сначала выберем, какие флаги будут участвовать в сигнале. Если число выбираемых флагов равно s, то выбор можно сделать С s m способами. Как мы уже знаем, с п о мощью данных s флагов можно передать

A k-1 m+k-1 сигналов. П о этому всего имеем С s m  A k-1 s+k-1 сигналов, передаваемых s флагами. А общее число сигналов равно

Пример 33. В некотором государстве каждые два человека отличаются набором зубов. Каково максимально возможное число жителей этого государства, если наибольшее число зубов у человека равно 32?

Решение. Эту задачу можно решить двумя способами. Первый способ заключается в том, что мы сначала ищем, сколько людей может иметь k зубов, а потом просуммируем полученные результаты от k=0 до k=32. Ясно, что k мест из 32 можно выбрать C k 32 способами. Поэтому

ровно k зубов имеют не более чем C k 32 жителей. А тогда общее число жителей не превосходит

C 0 32 +C 1 32 +…+C 32 32 .

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

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

Обозначим число возможных наборов k зубов через S k . Пред ы дущими рассуждениями мы доказали, что S 1 =2, S 2 = 4, S 3 =8. Допустим, что для некоторого k справедливо равенство S k =2 k , и докажем, что аналогичное равенство справедливо и для случая k + 1 зубов. Среди всех различных наборов, входящих в S k+1 , имеется ровно S k наборов, в которых отсутствует (k + 1)-й зуб, и столько же наборов, в которых (k + 1)-й зуб имеется. Поэтому

S k+1 =S k +S k =2S k =2 k+1 .

Таким образом, при возможных п зубах число всех людей, отличающихся набором зубов, равно 2 n . В нашем случае п = 32, поэтому мы получаем N =2 32 . Как известно, 2 10 == 1024 > 10 3 . Поэтому N > 4 • 10 9 , так что возможное население этого госуда р ства больше нынешнего населения всего земного шара.

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

C 0 32 +C 1 32 +C 2 32 +…+C 32 32 =2 32 .

Более того, из приведенного выше доказательства по индукции вытекает, что аналогичное равенство справедливо при любом п , то есть что имеет место формула

C 0 n +C 1 n +C 2 n + . +С n n =2 n .

Пример 34. Дана прямоугольная сетка квадратов размером m  n. Каково число различных дорог на этой сетке, ведущих из левого верхнего угла в правый нижний (рис. 1)? (Все звенья дороги предполагаются идущими или вправо, или вниз — без возвращений; сходная ситуация возникает, скажем, при выборе одного из кратчайших маршрутов между двумя городскими перекрестками.)

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

Можно было бы рассматривать число способов выбора не п вертикальных, а т горизонтальных отрезков и тогда мы получили бы ответ С m m+n нo формула (5) из пункта 3 показывает, что С m m+n = C n m+n .

Полученный результат можно использовать для вывода еще одной интересной формулы. Пусть наша сетка является квадра т ной, то есть имеет размеры п  п. Тогда из приведенного выше решения следует, что число различных дорог, соединяющих левый. верхний угол с правым нижним, равно C n 2n .

Источник