Комбинаторика

В 2010 г. в Федеральном перечне учебников, рекомендованных и допущенных к использованию
в школе, появилась новая линия учебников, выпущенная издательством «Бином»: М.И. Шабунин,
А.А. Прокофьев «Математика. Алгебра. Начала математического анализа. Профильный уровень». Предлагаем вашему вниманию главу «Комбинаторика» учебника для 11-го класса.

§ 1. Основные законы комбинаторики

На практике часто приходится выбирать из данного множества объектов подмножества элементов, обладающих некоторыми свойствами, располагать элементы одного или нескольких множеств в определенном порядке и т.д. Поскольку в этих задачах речь идет о тех или иных комбинациях элементов, их называют комбинаторными задачами. Область математики, изучающую комбинаторные задачи, называют комбинаторикой.
Различают несколько уровней решения комбинаторных задач. Начальным является поиск хотя бы одного расположения объектов, обладающего заданными свойствами (например, расположения восьми ферзей на шахматной доске, не бьющих друг друга). Если комбинаторная задача имеет несколько решений, то возникает вопрос о подсчете числа таких решений, об описании всех решений задачи. И, наконец, может возникнуть проблема поиска оптимального варианта решения в случае, если различные решения комбинаторной задачи отличаются друг от друга некоторыми параметрами.
Для подсчета числа решений комбинаторных задач используются формулы, основанные на двух простых правилах, называемых правилами суммы и произведения.
Правилом суммы называют следующее утверждение.

Если элемент x можно выбрать k способами, а другой элемент y можно выбрать m способами, то выбор «либо x, либо y» можно осуществить k + m способами.

В общем случае, когда удается разбить все изучаемые комбинации на несколько классов, причем каждая комбинация входит в один и только один класс, правило суммы формулируется следующим образом: общее количество комбинаций равно сумме комбинаций во всех классах. Это эквивалентно следующему утверждению: число элементов в объединении множеств X1, X2, ..., Xn таких, что Xi ∩ Xj = при i ≠ j равно сумме чисел элементов в каждом из множеств, то есть
| X1 ∪ X2 ∪ ... ∪ Xn | = | X1 | + | X2 | + ... + | Xn |.
Правилом произведения называют следующее утверждение.

Если элемент x можно выбрать k способами и если после каждого такого выбора элемент y можно выбрать m способами, то пару (x; y) в указанном порядке можно выбрать kжm способами.

Докажем это правило. По условию элемент x может быть выбран k способами. Пусть X = {x1; x2; ...; xk} — множество, из которого выбирается элемент x. По условию каждому выбору элемента x соответствует m способов выбора элемента y из некоторого множества Y. Пусть для каждого элемента xi, где 1 ≤ i ≤ k, выбираемые элементы y представляют некоторое подмножество {yi1; ...; yim} множества Y. Расположим все возможные для выбора пары (x; y) в виде прямоугольной таблицы:

В каждой строке этой таблицы содержится m пар, а всего строк k. Следовательно, таблица содержит всего kжm различных пар. В частности, если X = {x1; ...; xk}, Y = {y1; ...; ym} и выбор элемента y не зависит от способа выбора элемента x, то таблица имеет вид

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

Если элемент x1 можно выбрать n1 способами, и если после каждого такого выбора элемент x2 можно выбрать n2 способами, и т.д., и наконец, если после всех сделанных выборов элементов x1, x2, ..., xp – 1 элемент xp можно выбрать np способами, то упорядоченный набор (x1; x2; ...; xp) можно выбрать n1 ∙ n2 ∙... ∙ np способами.

Будем далее упорядоченный набор (x1; x2; ...; xk),состоящий из элементов x1, x2, ..., xk (необязательно различных), называть строкой длины k и считать две строки (x1; x2; ...; xk) и (y1; y2; ...; yk) различными в том и только том случае, если хотя бы для одного номера i, 1 ≤ i ≤ k, элемент xi отличен от yi.

○ Для доказательства правила произведения в общем случае используем индукцию по p.

Для p = 2 утверждение уже доказано выше.

Предположим, что правило произведения справедливо при выборе различных наборов, содержащих p = k элементов, и докажем, что оно верно в случае p = k + 1.
Любую строку длины k + 1
(x1; x2; ...; xk; xk + 1)            (1)
можно рассматривать как строку, состоящую из двух частей: строки (x1; x2; ...; xk), которую по предположению индукции можно выбрать n1∙n2∙...∙nk способами, и элемента xk + 1, который можно выбрать nk + 1 способами. Применяя уже доказанное выше правило для выбора упорядоченной пары, получаем, что число различных строк (1) будет
(n1∙n2∙...∙nk)∙nk + 1 = n1∙n2∙...∙nk + 1 . ●

Замечание. Правила суммы и произведения в комбинаторике сами по себе достаточно просты. Если Xi — множество состояний, из которых выбирается элемент xi, то ni — число элементов множества Xi (1 ≤ i ≤ p). При решении комбинаторных задач с применением этих правил основная трудность заключается в выборе множества Xi или элементов xi, то есть в формализации задачи.

Разберем несколько примеров на применение этих правил.

Пример 1. Сколько можно составить различных пятизначных чисел, чтобы любые две соседние цифры числа были различны?
► Пятизначному числу, записанному своими цифрами, можно поставить в соответствие строку (x1; x2; x3; x4; x5). В этой строке x1 — первая цифра пятизначного числа, для выбора которой имеется 9 возможностей (любая цифра, кроме 0), x2 — вторая цифра, для выбора которой имеется 9 возможностей (любая из цифр 0, 1, ..., 9, отличная от x1), ..., x5 — пятая цифра, для выбора которой имеется 9 возможностей (любая из цифр 0, 1, ..., 9, отличная от x4). Применяя правило произведения, находим, что искомое количество чисел равно 9∙9∙9∙9∙9 = 95. ◄

Пример 2. Сколько различных подмножеств имеет n-элементное множество A = {a1; a2; ...; an}?
► Пусть X — некоторое подмножество множества A. Поставим ему в соответствие строку (x1; x2; ...; xn), в которой каждый элемент xi,
1 ≤ i ≤ n, равен 1, если ai ∈ X, и равен 0, если ai ∈ X. В результате каждому подмножеству множества A будет соответствовать строка длины n, состоящая из нулей и единиц. И обратно, каждая строка длины n, состоящая из нулей и единиц, однозначно определяет некоторое подмножество X (например, в случае n = 4 строка (0; 1; 0; 1) определяет подмножество {a2; a4}). По правилу произведения получаем, что число различных строк длины n, состоящих из нулей и единиц, равно 2∙2∙...∙2 = 2n. Значит, число различных подмножеств n-элементного множества будет также равно 2n. ◄

Часто в задачах приходится применять сразу оба правила комбинаторики.
Рассмотрим задачу, в которой используются игральные кости. Игральная кость представляет собой кубик, на каждой грани которого проставлены маркирующие очки 1, 2, 3, 4, 5, 6. Сумма очков на противоположных гранях равна 7. Если в результате бросания «кость падает гранью 1 вверх», то говорят: «выпало 1 очко»; если «кость падает гранью 2 вверх», то говорят: «выпало 2 очка»; и т. д.

Пример 3. Бросают две игральные кости. Сколькими способами они могут упасть так, что либо на каждой кости выпадет четное число, либо на каждой кости выпадет нечетное число очков?

► Будем записывать результат бросания двух игральных костей парой чисел (x1; x2), где x1 и x2 — количество очков, выпавших на первой и второй кости соответственно. Пусть k — число способов выпадения на каждой кости четного числа очков, m — число способов выпадения на каждой кости нечетного числа очков. Тогда, по правилу суммы, искомое число равно k + m.
Имеется три способа выпадения четного числа x1 на первой кости (x1 ∈ {2; 4; 6}) и три способа выпадения четного числа x2 на второй кости (x2 ∈ {2; 4; 6}). Тогда, по правилу произведения, имеется k = 3∙3 = 9 способов получить набор (x1; x2), в котором числа x1 и x2 — четные. Аналогично, существует m = 3∙3 = 9 способов получить набор (x1; x2), в котором числа x1 и x2 — нечетные. Следовательно, искомое число способов равно k + m = 9 + 9 = 18. ◄

Рассмотрим произвольное n-элементное множество X. Множество называется упорядоченным, если каждому его элементу поставлено в соответствие некоторое число (номер элемента) от 1 до n так, что различным элементам соответствуют различные номера. Всякое конечное множество можно сделать упорядоченным, если, например, переписать все элементы в некоторый список (x1; x2; ...; xn), а затем поставить в соответствие каждому элементу номер места, на котором он стоит в списке. Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком.

Пример 4. Найти число различных способов, которыми можно упорядочить данное n-элементное множество X.
► Будем последовательно выбирать элементы множества X и размещать их в определенном порядке на n местах. На первое место можно поставить любой из n элементов. После того, как заполнено первое место, на второе место можно поставить любой из оставшихся n – 1 элементов и т.д. По правилу произведения все n мест можно заполнить
n∙(n – 1)∙(n – 2)∙...∙2∙1 = n!
способами. Следовательно, n-элементное множество можно упорядочить n! способами. ◄

Пример 5. Сколько существует различных, отличающихся очередностью доставки, вариантов разноса корреспонденции по 6 разным адресам?
► Занумеруем адреса цифрами от 1 до 6. Каждому варианту доставки можно сопоставить набор из шести цифр, например, (3; 4; 5; 6; 1; 2). Такой набор означает, что сначала корреспонденция доставляется по третьему адресу, затем по четвертому, пятому, шестому, первому и второму. Всего различных вариантов доставки, то есть наборов, отличающихся порядком следования цифр, будет 6! = 720. ◄

Задачи

1. Сколькими способами можно расставить на книжной полке подряд друг за другом книги десятитомного собрания сочинений?
2. 1) Сколькими способами можно сделать трехцветный флаг с вертикальными полосами одинаковой ширины и различных цветов, если имеется материя 7 различных цветов?
2) Сколькими способами можно сделать флаг, содержащий 7 вертикальных полос одинаковой ширины красного, белого или синего цвета, причем любые две соседние полосы должны быть разных цветов?
3. В некотором государстве нет двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения этого государства? Напомним, что у человека может быть не более 32 зубов.
4. Сколько существует четырехзначных чисел, в которых две единицы стоят рядом, а остальные цифры различны и не равны 1? А пятизначных?
5. Сколькими способами можно на шахматной доске расставить 8 ладей, чтобы они не били друг друга, если:
а) ладьи неразличимы;
б) ладьи различимы (например, пронумерованы)?
6. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево? А шестизначных?

Ответы: 1. 10!  2. 1) 210; 2) 3∙26 = 192.  
3. 232. 4. 200; 1848.  5. а) 8! = 40 320; б) (8!)2.  
6. 900; 900.

§ 2. Основные формулы комбинаторики

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

В примере 2 § 1 было найдено общее число различных подмножеств n-элементного множества. В этом пункте найдем количества его различных k-элементных подмножеств и различных упорядоченных k-элементных подмножеств.
Например, из элементов множества {1; 2; 3; 4} можно составить 6 подмножеств из двух элементов: {1; 2}, {1; 3}, {1; 4}, {2; 3}, {2; 4}, {3; 4}, и 12 упорядоченных подмножеств из двух элементов, которые можно рассматривать как упорядоченные пары чисел: (1: 2), (2; 1), (1; 3), (3; 1), (1; 4), (4; 1), (2; 3), (3; 2), (2; 4), (4; 2), (3; 4), (4; 3).
В этом параграфе будут рассмотрены две схемы составления из n-элементного множества упорядоченных наборов, содержащих k элементов. В данном пункте будет применена схема 1 (без возвращений), а в следующем — схема 2
(с возвращениями).
Схема 1 (без возвращений). В мешок помещаются n карточек, на каждой из которых записано название одного элемента множества X, причем разные карточки соответствуют разным элементам. Далее, карточки по одной извлекаются из мешка без возвращения назад и элементы записываются в порядке извлечения. После k извлечений запись представляет собой строку длины k без повторений, состоящую из элементов множества X (точнее говоря, из их названий).
Определение. Упорядоченные k-элементные подмножества, содержащие k элементов из данного n-элементного множества, называют размещениями без повторений из n элементов по k. Их число обозначают (A — первая буква фр. arrangement — размещение).
Два размещения отличаются либо составом элементов, либо порядком следования элементов.

Теорема 1 (о числе размещений без повторений). Число размещений без повторений из n элементов по k определяется по формуле

(1)

○ Данная задача имеет решение только при k ≤ n.
Отведем для элементов размещения строку ( 1;  2; ...;  k) длины k. Так как на первую позицию можно поместить любой из n элементов данного множества, а на вторую — любой из n – 1 оставшихся элементов, то, по правилу произведения, число различных способов для заполнения первых двух позиций строки равно n(n – 1). Далее аналогично: на третью можно поместить любой из n – 2 элементов, а, по правилу произведения, различных способов для заполнения первых трех позиций получается n(n – 1)(n – 2) и т.д. Окончательно получаем, что общее число строк длины k, формируемых из различных элементов n-элементного множества, равно
= n∙(n-1)∙...∙(n-k+1)
Отсюда получаем

Пример 1. Сколькими способами из 25 учеников класса можно выделить актив в следующем составе: культорг, физорг и редактор стенгазеты?
► Требуется выделить упорядоченные трехэлементные подмножества множества, содержащего 25 элементов, то есть найти число размещений без повторений из 25 элементов по 3. По формуле (1) находим

Определение. Размещение из n элементов по n называется перестановкой из n элементов. Их число обозначают Pn (от фр. permutation — перестановка).
Например, P3 = 6, так как из элементов 1, 2, 3 можно составить шесть различных перестановок:

Для нахождения числа Pn заметим, что перестановка без повторений из n элементов — это то же самое, что размещение без повторений из n элементов по n, то есть Поэтому для отыскания значения Pn в формуле (1) положим
k = n:

Пример 2. Сколько существует пятизначных чисел, не кратных пяти и не содержащих одинаковых цифр, составленных из цифр 1, 2, 3, 4, 5?
► Способ I. Из пяти различных цифр можно составить P5 пятизначных чисел. Эти числа не должны быть кратны 5, то есть не могут оканчиваться цифрой 5. Если же цифру 5 поставить на последнее место, то остальные цифры могут распределиться по разрядам числа P4 способами. Поэтому условию задачи удовлетворяет
P5 – P4 = 5! – 4! = 120 – 24 = 96 чисел.
Способ II. Как уже было отмечено в первом способе, последняя цифра в записи числа может быть любой из данных, кроме 5. Следовательно, последний разряд может быть заполнен 4 способами. Соответственно, первые четыре разряда могут быть заполнены 4! способами. Всего, по правилу произведения, получается 4ж4! = 96 способов, то есть 96 чисел. ◄

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

Определение. Неупорядоченные подмножества, содержащие k элементов из данного n-элементного множества, называют сочетаниями без повторений из n элементов по k, а их число обозначают символом (от фр. combination — сочетание).

Замечание. Отличие размещения без повторений от сочетания без повторений состоит в том, что в первом случае важен порядок выбора элементов (то есть их место в соответствующем упорядоченном наборе), а во втором — нет.
В учебнике 10-го класса символ использовался для обозначения биномиального коэффициента. Обозначим через Nk число всех неупорядоченных k-элементных подмножеств n-элементного множества X. Покажем, что число Nk или, что то же самое, число сочетаний без повторений из n элементов по k совпадает со значением соответствующего биномиального коэффициента.

Теорема 2 (о числе сочетаний без повторений). Число всех неупорядоченных k-элементных подмножеств n-элементного множества равно
          (3)
○ Отметим, что N0 = 1, то есть каждое множество X имеет лишь одно подмножество, не содержащее элементов (пустое множество), и

Значит,
Количество сочетаний Nk и размещений связаны равенством так как упорядочить каждое сочетание (получив при этом размещение) можно k! способами. Отсюда Используя (1), получаем

Пример 3. На плоскости проведены n прямых, среди которых нет ни одной пары параллельных прямых и ни одной тройки прямых, пересекающихся в одной точке. Найти:
1) число точек пересечения этих прямых;
2) число треугольников, образованных этими прямыми.
► 1) Число точек пересечения прямых равно числу способов выбора неупорядоченной пары прямых, то есть
2) Аналогично, каждый треугольник определяется тройкой прямых, поэтому общее число треугольников равно

Пример 4. Сколькими способами можно расставить на 32 черных полях шахматной доски 12 белых и 12 черных шашек?
► Поля для белых шашек можно выбрать способами. После этого остается 20 полей, на которых можно способами выбрать поля для черных шашек. Используя правило произведения, получаем, что искомое количество способов расстановки равно

Пример 5 (задача о книжной полке). На книжной полке стоит n книг. Сколькими способами можно выбрать из них k книг так, чтобы в их число не попали никакие две стоящие рядом?
► Воспользуемся следующим приемом. Так как положение книг на полке можно задать, пронумеровав их, то, согласно имеющемуся расположению, каждому выбору с полки k книг можно будет поставить в соответствие строку длины n, состоящую из k единиц и m = n – k нулей, в которой единицы стоят в позициях, соответствующих порядковым номерам выбираемых книг на полке. И обратно, каждой такой строке соответствует способ выбора k книг с полки из n книг.
Например, при таком выборе 3 книг из 8 стоящих на полке, строке (0; 1; 0; 0; 1; 0; 0; 1) соответствует выбор 2, 5 и 8-й книг.
Согласно условию задачи, нас интересуют только такие строки, в которых никакие две единицы не стоят рядом. Для решения данной задачи при формировании строк возьмем сначала m нулей. Тогда для единиц имеется m + 1
место, из которых два находятся по краям и m – 1 место в промежутках между нулями. На любое из них можно поставить одну из k единиц. Следовательно, это число способов равно

Значит, выбрать k книг так, чтобы в их число не попали никакие две стоящие рядом, можно способами.
Например, в случае десятитомного издания, тома которого стоят в некотором фиксированном порядке, извлечь 4 книги, чтобы в число извлеченных не попали никакие две стоящие рядом, можно способами.
Заметим, что задача разрешима, если k ≤ n – k + 1,
то есть 2k ≤ n + 1. ◄

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

Рассмотрим теперь вторую схему выбора элементов.
Схема 2 (с возвращением). В мешок помещаются n карточек, на каждой из которых записано название одного элемента множества X, причем разные карточки соответствуют разным элементам. Карточки по одной извлекаются из мешка, названия элементов записываются в порядке извлечения, а далее карточки возвращаются назад в мешок. Тем самым получаем, что на каждом шаге может быть извлечен любой элемент множества X. После k извлечений запись представляет собой строку длины k, возможно — с повторениями, состоящую из элементов множества X (точнее говоря, состоящую из их названий).

Определение. Упорядоченные наборы длины k, составленные из элементов n-элементного множества с использованием схемы с возвращением, называют размещениями с повторениями из n элементов по k. Их общее число обозначают

Теорема 3 (о числе размещений с повторениями). Число размещений с повторениями из n элементов по k определяется по формуле

(4)

○ Данная задача имеет решение при любом значении k. Проведем рассуждения аналогичные тем, которые были использованы при выводе формулы (1). Так как каждую из k позиций соответствующей строки можно заполнить n способами, то из правила произведения следует, что

Пример 7. Имеется 5 различных стульев и
7 рулонов обивочной ткани различных цветов. Сколькими способами можно выполнить обивку стульев?
► Так как стулья различны, то их можно расположить в определенном порядке, и каждому способу обивки будет соответствовать строка длины 5, составленная из данного 7-элементного множества цветов ткани. Число таких строк находится по формуле (4)

Пусть есть k-элементное множество X и n-элементное множество Y. Для подсчета числа отображений f множества X в множество Y (f: X → Y) можно поступить следующим образом. Так как каждый элемент xi ∈ X, 1 ≤ i ≤ k, может быть отображен в любой из n элементов множества
Y = {y1; y2; ...; yn}, то каждому отображению соответствует строка длины k, составленная из элементов множества Y. И наоборот, каждой такой строке длины k соответствует отображение f:
X → Y. Используя формулу (4) получаем, что число отображений k-элементного множества в n-элементное множество равно

Пример 8. Сколько существует способов размещения n различных предметов по m различным ящикам?
► Пронумеруем предметы и ящики. Тогда каждому размещению соответствует строка длины n, каждая компонента которого может быть заполнена m способами, так как каждый предмет может быть помещен в любой из m ящиков. Тогда, по формуле (4), искомое число размещений n различных предметов по m различным ящикам равно

Рассмотрим размещение с повторениями (или соответствующую ему строку длины k), в которое вошли m групп элементов. Пусть число элементов x1 (элементов первой группы) равно n1, число элементов x2 (элементов второй группы) равно n2, ..., число элементов xm (элементов m-й группы) равно nm и n1 + n2 + ... + nm = k. Соответственно, упорядоченный набор (n1; n2; ...; nm) назовем составом этой строки. Например, строка
(x1; x2; x1; x2; x3; x4; x2; x3) имеет состав (2; 3; 2; 1). Переставляя между собой элементы такой строки, будем получать новую строку (размещение с повторениями) того же самого состава.

Определение. Размещения с повторениями, имеющие один и тот же состав и отличающиеся друг от друга лишь порядком компонент, называются перестановками с повторениями данного состава. Их число обозначают символом
P(n1; n2; ...; nm), где n1 + n2 + ... + nm = k.

Теорема 4 (о числе перестановок с повторениями). Пусть n1, n2, ..., nm — целые неотрицательные числа, причем n1 + n2 + ... + nm = k. Число перестановок с повторениями данного состава определяется по формуле

(5)

○ Отведем для элементов размещения с повторениями строку ( 1;  2; ...;  k) длины k. Среди этих k позиций выберем n1 позиций, на которые поместим элементы первого вида. Это можно сделать способами. Среди оставшихся k – n1 позиций выберем n2 позиций, на которые поместим элементы второго вида (это можно сделать способами), и т.д. Общее число способов (соответственно, перестановок) по правилу произведения будет равно

Поскольку
n1 + n2 + ... + nm = k, то (k – n1 – ... – nm)! = 0! = 1.
Следовательно, справедлива доказываемая формула (5). ●

Пример 9. Сколькими способами можно расставить белые фигуры: 2 коня, 2 слона, 2 ладьи, 1 ферзя и 1 короля на первой линии шахматной доски?
► Для решения задачи найдем число перестановок с повторениями, имеющих заданный состав (2; 2; 2; 1; 1). По формуле (5) получаем, что искомое число перестановок с повторениями равно

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

В предыдущем пункте рассматривались перестановки с повторениями, имеющие одинаковый фиксированный состав (n1; n2; ...; nm), где n1 + n2 + ... + nm = k. В данном пункте найдем число различных способов разбиения числа k на m целых неотрицательных слагаемых.
Каждый такой способ разбиения числа k на m целых неотрицательных слагаемых представляет собой некоторый упорядоченный набор из k элементов, выбираемых из m видов одинаковых элементов. Такой набор будем называть сочетанием с повторениями из k элементов, выбираемых из m видов одинаковых элементов.
Решим сначала пример 10, а затем найдем число способов разбиения числа k на m целых неотрицательных слагаемых в общем случае.

Пример 10. Сколькими способами можно представить число 6 в виде суммы трех целых неотрицательных слагаемых.
► Воспользуемся следующим приемом. Представим число 6 как 6 единиц, разбитых на 3 группы (причем группа может и не содержать единиц). Чтобы различать группы, поставим между ними нули (всего потребуется 2 нуля). Тогда каждому разложению числа 6 в виде суммы слагаемых n1, n2, n3, где n1 + n2 + n3 = 6, будет соответствовать набор из 6 единиц и 2 нулей (и наоборот, каждому такому набору — разложение). Например, набору 11101011 соответствует разложение 3 + 1 + 2 = 6 (и наоборот), а набору 11001111 соответствует разложение 2 + 0 + 4 = 6
(и наоборот).
Следовательно, искомое число способов разложения числа 6 в виде суммы трех целых неотрицательных слагаемых будет равно числу различных наборов из шести единиц и двух нулей. По формуле (5) находим

Рассуждая аналогично в общем случае, представим число k в виде k единиц, разбитых на
m групп, причем группа может и не содержать единиц, для этого между группами поставим нули (всего получится m – 1 нулей). Тогда каждому разложению k в виде суммы слагаемых n1, n2, ..., nm будет соответствовать набор из k единиц и m – 1 нулей, то есть


(и наоборот, каждому такому набору — разложение). Всего таких наборов
          (6)

Для обозначения общего числа сочетаний с повторениями из k элементов по m используется символ В соответствии с полученным выше результатом:
          (7)

Пример 11. Сколькими способами можно составить набор из 8 пирожных, если имеется 4 вида пирожных?
► Поскольку порядок пирожных в наборе не играет роли, то каждый набор задается строкой длины 8 из 4 элементов (названий видов пирожных), причем порядок элементов в строке не играет роли. Иными словами, нам надо найти число различных составов таких строк, то есть число сочетаний с повторениями из 4 элементов по 8. По формуле (7) имеем

Пример 12. Сколько существует способов размещения n одинаковых предметов по m различным ящикам?
► Будем рассуждать так же, как рассуждали при выводе формулы (6). Предположим, что n элементов разместили по ящикам так, что в первый, второй, ..., m-й ящик попало соответственно n1, n2, ..., nm предметов. Такому размещению поставим в соответствие набор из n и m – 1 нулей, то есть

(и наоборот, каждому такому набору — размещение). Тогда число таких размещений равно
◄

Задачи

1. 1) Сколькими способами можно расставить 25 учеников в одну шеренгу?
2) Сколькими способами можно рассадить 25 учеников за 15 парт (считая, что за каждой партой может сидеть не более двух учеников)?

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

3. Сколько шестизначных чисел, кратных 5, можно составить из цифр 0, 1, 2, ..., 9 при условии, что в записи числа нет одинаковых цифр?

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

5. Хоккейная команда состоит из 2 вратарей, 7 защитников и 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку, состоящую из вратаря, двух защитников и трех нападающих?

6. На окружности отмечено 9 точек. Сколько можно построить:
1) хорд, соединяя любые две из них;
2) различных треугольников с вершинами в этих точках;
3) выпуклых четырехугольников с вершинами в этих точках?

7.  Для проведения письменного экзамена по математике надо составить 4 варианта по 7 задач в каждом. Сколькими способами можно разбить 28 задач на 4 варианта?

8. На линии расположены n стульев. Сколькими способами можно убрать три стула так, чтобы не были убраны:
1) три рядом стоящих стула;
2) никакие два рядом стоящих стула?

9. Сколькими способами могут распределиться 15 пронумерованных бильярдных шаров по 6 лузам?

10. Сколько делителей имеет число 20072007?

11. Сколько слов можно получить, переставляя буквы слова:
1) винегрет;
2) математика?

12. Сколько существует способов вынуть 10 карт из колоды, содержащей 52 карты, так, чтобы среди этих карт:
1) был хотя бы один туз;
2) ровно один туз;
3) было не менее двух тузов;
4) ровно два туза?

13. 1) Сколькими способами можно разложить 15 книг по пяти бандеролям по 3 книги в каждой (порядок бандеролей неважен)?
2) Сколькими способами можно разложить
9 книг по четырем бандеролям по 2 книги и одной бандероли с 1 книгой (порядок бандеролей неважен)?

14. Бросают n игральных костей. В результате получают n чисел от 1 до 6. Сколько может получиться различных результатов, если результаты, отличающиеся друг от друга лишь порядком очков, считаются одинаковыми?

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

16. Сколькими способами можно разделить 12 конфет «Белочка», 15 конфет «Мишка» и 6 конфет «Маска» между 5 ребятами?

17. Сколько решений имеет уравнение
x1 + x2 + ... + x7 = 10,
где:
1) x1, x2, ..., x7 — целые неотрицательные числа;
2) x1, x2, ..., x7 — натуральные числа.

Ответы:

Прокофьев А. , Шабунин М.