Методическая разработка темы "Комбинаторика"
методическая разработка по алгебре (11 класс) по теме

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ И ТЕОРИИ ВЕРОЯТНОСТЕЙ

ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ

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

ВВЕДЕНИЕ

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

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

                             I. Правило суммы

Рассмотрим следующий пример. Если на одной полке книжного шкафа стоит 30 различных книг, а на другой — 40 различных книг (и нет таких, как на первой полке), то выбрать одну книгу из стоящих на этих полках можно 30+40=70 способами. Обобщением этого примера является, следующее утверждение  называемое правилом суммы.

Если элемент а можно выбрать т способами, а элемент Ь-n способами, причем любой выбор элемента а отличен, от любого выбора элемента Ь, то выбор «а или Ь» можно сделать m+n способами. На языке теории множеств это правило формулируется следующим образом:

Теорема 1. Если пересечение конечных множеств A и B  пусто, то число элементов в их объединении равно сумме чисел элементов множеств A и B:

                                                        п(АВ)=п(А)+п(В).                     (1)

С помощью метода математической индукции из этой теоремы получаем следствие.

Следствие 1. Если конечные множества A1, A2,..., AK  попарно не пересекаются, то имеет место равенство

                           n(А1А2...Аk)=n(А1)+n(А2)+...+n(Аk).             (2)

Пример 1. При формировании экипажа космического корабля имеется 10 претендентов на пост командира экипажа, 20 — на пост бортинженера и 25 — на пост космонавта-исследователя. Ни один кандидат не претендует одновременно на два поста. Сколькими способами можно выбрать одну из кандидатур или командира, или бортинженера, или космонавта-исследователя?   

Решение. Обозначим множество кандидатов на пост командира корабля через А, множество кандидатов на пост бортинженера через В и множество кандидатов на пост инженера-исследователя через С. Тогда по условию

n(A)=10, n(В)=20, n(С)=25.

Кроме того,

AB=, AC=, BC=.

По формуле (2) имеем:

                        n(АBC)=n(А)+n(B)+n(C)=55 способов.         

                              II. Правило произведения

Начнем с примера.

Пример 2. Пусть существует три кандидата K1, K2, K3 на место командира корабля и два кандидата B1 и В2 на место бортинженера. Сколькими способами можно сформировать экипаж корабля, состоящий из командира и бортинженера?

Решение. Командира корабля можно выбрать тремя способами. После выбора командира еще двумя способами можно выбрать бортинженера, поэтому общее число способов, которыми можно составить экипаж, находится произведением 32=6. Графическая иллюстрация этого решения приведена на рисунке 1.

                                                                          Выбор

                                               Выбор         бортинженера        ЭКИПАЖ

                                    командира                                

                                                                                                                 (K1, B1)

                                                                                                           (K1, B2)

       Начало                                                                            (K2, B1)

                                                                                                                 (K2, B2)

                                                                                              (K3, B1)

                                                                                              (K3, B2)            

рисунок 1

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

Обобщением этого примера является следующее утверждение, называемое правилом произведения.

Пусть множество А состоит из элементов {a1, a2,…, am} и множество B — из элементов {b1, b2,…, bk}. Пусть из множества A выбирается любой из его т элементов и независимо от него из множества В выбирается любой из его k элементов. Выбранные элементы образуют пару (ai, bj), где aiA, bjB. Множество этих пар можно записать в виде следующей

таблицы:

(a1, b1), (a1, b2), …,  (a1, bk),

(a2, b1), (a2, b2), …,  (a2, bk),

.  .  .  .  .  .  .  .   .  .  .  .  .  .  .

  (am, b1), (am, b2), …,  (am, bk).

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

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

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

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

N = n(А) • п(В).

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

Следствие 2. Если имеется k конечных множеств A1, A2,..., AK то число N всевозможных наборов (a1, a2, …, ak), где a1A1, a2A2, …, akAk, равно

N=n(A1)n(A2)...n(Ak).

Пример 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. В столовой предлагают два различных первых блюда a1 и а2, три различных вторых блюда b1, b2, b3  и два вида десерта с1   и   c2. Сколько различных обедов из трех блюд может предложить столовая?

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

n(A)=2, n(В)=3, n(С)=2.

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

N=n(A)n(B)n(C)=l2

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

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

                                                                                    блюдо                  

                                                                                                                                                                 (a1, b1, c1)

                                                                                                                                                                 (a1, b1, c2)

                                          Первое                                                            

                                   бюдо                                                                                        

                                                                                                                                      (a1, b2, c1)

                                                                                                                                                                 (a1, b2, c2)

                                                                                                                                                                 (a1, b3, c1)

Начало                                                                                                                          (a1, b3, c2)

                                                                                                                                                                 (a2, b1, c1)

                                                                                                                                                                 (a2, b1, c2)

                                                                                                                                                                 (a2, b2, c1)

                                                                                                                                                                 (a2, b2, c2)

                                                                                                                                                                 (a2, b3, c1)               

                                                                                                                                                                 (a2, b3, c2)

рисунок 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 обозначают Akn.

Формула для числа Akn получается обобщением результата, полученного в примере 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 называются перестановками.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6, 10, 14, 15, 21, 35); число делителей, составленных из произведения трех простых множителей, равно С34=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 элемента. Они будут иметь вид:

aaa,      baa,      bba,

aab,      abb,      bbb.

                                                                 aba,      bab,

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

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

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

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

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

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

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

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

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

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

Пусть k=m+1. По предположению имеется nm возможностей разместить по 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 при каждом фиксированном п.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Число всех таких перестановок с повторениями принято обозначать Cn(n1, n2,…,nk), и оно может быть найдено по формуле

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

Таким  образом, n1!n2!…nk!Pn(n1, n2,…,nk)=n!, откуда следует формула для числа перестановок с повторениями.

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

Решение.

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

Решение.

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

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

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

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

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

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

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

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

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

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

aa,     ac,      bc,

ab,      bb,      cc.

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

aaa,       aac,       abc,       acc,       bcc,

aab,       abb,       bbb,       bbc,       ccc.

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

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

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

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

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

Отсюда имеем

Поскольку (смотри пример 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, получаем, что число различных способов, которыми шесть пассажиров могут распределиться в трех вагонах, равно:

A63(П)=36=729.

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

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

C63(П)=C68=C28=28.

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

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

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

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

28!/ (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, то выбор можно сделать Сsm способами. Как мы уже знаем, с помощью данных s флагов можно передать

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

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

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

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

C032+C132+…+C3232.

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

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

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

Sk+1=Sk+Sk=2Sk=2k+1.

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

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

C032+C132+C232+…+C3232=232.

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

C0n+C1n+C2n + ... +Сnn =2n.

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

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

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

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

                               m                                                                        n                          An

                                                                                A0   

                Рисунок 1                                                                           Рисунок 2

Вместе с тем число этих дорог можно подсчитать иначе. Рассмотрим диагональ, идущую из нижнего левого угла в верхний правый, и обозначим вершины, лежащие на этой диагонали, через A0, A1, …, An. Так как каждая дорога обязательно проходит через одну — и притом единственную — точку этой диагонали, то общее число дорог есть сумма числа дорог, идущих через точку A0, через точку A1, через точку A2, ..., через точку An.                         Найдем число возможных дорог, идущих через точку Ak (0kп). Если нумерация точек произведена снизу вверх, как это показано на рис. 47, то точка Ak отстоит от нижней горизонтали на расстоянии k, считая за единицу измерения длину стороны квадрата сетки. От правой вертикали ее отделяют тогда п—k горизонтальных отрезка.                                       Дорог, соединяющих верхний левый угол с точкой Ak, будет тогда Ck(n-k)+k=Ckn, а дорог, соединяющих точку Ak с нижним правым углом, будет Cn-kk+(n-k) = Сn-kn = Сkn (это видно из рассмотрения равных прямоугольников, противоположными вершинами которых служат верхний левый угол исходного квадрата и точка Аk и соответственно точка Ak и нижний правый угол квадрата). Поэтому общее число дорог, соединяющих верхний левый угол с нижним правым и проходящих через Ak, равно (Ckn)2 . Но тогда общее число всех дорог равно сумме

(C0n)2+(C1n)2+(C2n)2+... +(Cnn)2.

Сравнивая полученную сумму с найденным выше выражением для числа дорог, мы придем к формуле:

(C0n)2+(C1n)2+(C2n)2+... +(Cnn)2=Cn2n.

B1

B2

B1

B2

K2

0

K3

B2

K1

B1

a2

O

a1

С2

С1

С2

С1

С2

С1

С2

С1

С2

С1

С2

С1

b3

b2

b1

b3

b2

b1