Элементы комбинаторики

Московский государственный технический университет
имени Н.Э. Баумана
А.И. Белоусов, П.А. Власов
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Методические указания
к выполнению домашнего задания
Москва
Издательство МГТУ им. Н.Э. Баумана
2012

УДК 519.1
ББК 22.141
Б43
Рецензент Р.С. Исмагилов
Б43
Белоусов А.И.
Элементы комбинаторики : метод. указания к выполнению
домашнего задания / А.И. Белоусов, П.А. Власов. – М.: Изд-во
МГТУ им. Н.Э. Баумана, 2012. – 53, [3] с. : ил.
Методические указания содержат краткий теоретический материал,
необходимый для выполнения домашнего задания по курсу «Дискретная математика». Рассмотрены примеры решения задач, приведены
задачи для самостоятельной работы.
Для студентов 2-го курса, обучающихся по специальности ИУ-7.
Рекомендовано Учебно-методической комиссией НУК ФН МГТУ
им. Н.Э. Баумана.
УДК 519.1
ББК 22.141
Учебное издание
Белоусов Алексей Иванович
Власов Павел Александрович
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Методические указания
к выполнению домашнего задания
Редактор В.М. Царев
Корректор
Н.А. Фетисова
Компьютерная верстка В.И. Товстоног
Подписано в печать 16.03.2011. Формат 60×84/16.
Усл. печ. л. 3,26. Тираж 300 экз. Изд. №29.
Заказ
Издательство МГТУ им. Н.Э. Баумана.
Типография МГТУ им. Н.Э. Баумана.
105005, Москва, 2-я Бауманская ул., 5.
c
⃝МГТУ им. Н.Э. Баумана, 2012

1. КОМБИНАТОРНЫЕ ОБЪЕКТЫ
Комбинаторика – раздел математики, изучающий конфигурации конечных множеств. Под словом «конфигурация» понимается
некоторая совокупность элементов конечного множества, обладающая заданными свойствами. Например, наборы элементов данного множества, составленные с учетом порядка входящих в него
элементов или без него; содержащие произвольное или, наоборот,
заданное число элементов; содержащие или не содержащие заранее определенные элементы. К основным задачам комбинаторики относят подсчет числа конфигураций, обладающих определенными свойствами, а также описание алгоритма их перечисления.
С учетом этого словосочетание «комбинаторный объект» будем
использовать в качестве синонима термина «конфигурация».
1.1. Основные понятия
Пусть M – множество, состоящее из n элементов. Без ограничения общности будем считать, что M = {1, 2, . . . , n}; в противном случае элементы M можно перенумеровать и рассматривать
не сами объекты, а их номера.
Размещением с повторениями из n по m будем называть кортеж (упорядоченный набор)
(x1, x2, . . . , xm) ,
(1.
.1)
где xi ∈M, i = 1; m. Число размещений с повторениями из n по
m будем обозначать ˜
Am
n . Легко видеть, что множество всех таких
размещений является m-й декартовой степенью множества M и,
3

следовательно,
˜
Am
n = |Mm| = |M|m = nm.
(1.
.2)
Стоит специально отметить, что два размещения считаются
равными в том и только том случае, когда имеют одинаковую длину и у них совпадают соответствующие компоненты. При этом,
если поменять местами две компоненты, получим, вообще говоря,
другое размещение.
Размещением без повторений из n по m будем называть
кортеж
(x1, x2, . . . , xm) ,
(1.
.3)
где xi ∈M, i = 1; m, и xi ̸= xj при i ̸= j. Последнее условие означает, что все компоненты соответствующего набора должны быть
различны. Очевидно, что размещение без повторений существует
лишь в случае m ⩽n; при m = n кортеж (1.3) будем называть
перестановкой длины n. Можно показать, что число размещений
без повторений из n по m дается формулой
Am
n = n(n −1) · . . . · (n −m + 1),
(1.
.4)
из которой следует, что число перестановок длины n
Pn = An
n = n(n −1) · . . . · 1 = n!.
Замечание 1.1. В основе доказательства соотношений (1.2) и (1.4)
лежит следующий очень простой прием, удобный для запоминания. Поскольку множество M состоит из n элементов, каждую из m компонент
кортежа (1.3) можно заполнить одним из n способов, следовательно, число способов составить кортежи (1.2)
n · . . . · n



m раз
= nm.
В случае размещения без повторений на первую позицию кортежа
(1.3) можно поставить любой из n элементов множества M, на вторую
(которая должна отличаться от первой) – любой из оставшихся n −1
элементов, на третью – любой из n −2 и т. д. Таким образом, число
размещений без повторений составит
n(n −1) · . . . · (n −m + 1). #
4

Сочетанием без повторений из n по m называется любое mэлементное подмножество множества A. В определении предполагается, что в отличие от размещений вхоящие в сочетание элементы не упорядочены каким-либо образом, и сочетание полностью
определяется лишь их составом. Можно показать, что число сочетаний без повторений из n по m дается формулой1
Cm
n =
n!
m!(n −m)!.
Пример 1.1. a. Преподаватель пришел на экзамен в плохом настроении и решил в группе из 20 человек поставить пять «двоек».
Сколькими способами он может выбрать своих жертв?
Р е ш е н и е. Очевидно, что набор жертв полностью определяется составом студентов; при этом порядок, в котором они покинут
экзаменационную аудиторию, не имеет значения. Следовательно,
каждый такой набор можно интерпретировать как сочетание без
повторений из 20 по 5. Таким образом, число возможных способов
сформировать группу двоечников
C5
20 =
20!
5!(20 −5)! = 15 504.
б. Найти число способов, которыми можно рассадить 11 человек на одну лавку.
Р е ш е н и е. Каждый из интересующих нас способов однозначно определяется кортежем (x1, . . . , x11), где xi – номер человека,
сидящего на i-м месте, i, xi = 1; 11. По смыслу задачи указанный
кортеж является размещением (порядок, в котором рассажены люди, имеет значение) без повторний (один человек не может сесть
более чем на одно место) из 11 по 11. Таким образом, число способов рассадить 11 человек на лавке P11 = 11! = 39 916 800.
в. В мешке Деда Мороза находится 20 различных подарков.
Сколькими способами можно раздать подарки 17 детям при условии, что каждый ребенок получает ровно один подарок?
Р е ш е н и е.
Для решения задачи удобно перенумеровать
детей числами 1, . . . , 17, а подарки – числами 1, . . . , 20. В этом
1Числа Cm
n являются коэффициентами при одночленах ambn−m в разложении бинома (a+b)m, поэтому их называют биномиальными коэффициентами.
5

случае каждый из способов раздать подарки можно описать кортежем (x1, . . . , x17), где xi ∈{1, . . . , 20} – номер подарка, получаемого i-м ребенком. По содержанию задачи этот кортеж является
размещением (порядок важен, так как он определяет, какому ребенку достанется тот или иной подарок) без повторений (все подарки различны) из 20 по 17. Таким образом, искомое число A17
20 =
= 20 · 19 · . . . · 4 = 405 483 668 029 440 000 #.
Пример 1.2. а. Найти число способов, которыми можно составить хоровод из 11 девушек.
Р е ш е н и е. Аналогично задаче 1.1, б можно попробовать
описать хоровод кортежем (x1, . . . , x11), однако в отличие от лавки
хоровод замкнут (не имеет начала и конца). Это означает, что при
циклической перестановке элементов x1, . . . , x11 мы можем получить другое размещение, которое, однако, будет описывать тот
же хоровод. Таким образом, при указанном подходе соответствие
между хороводами и размещениями не является однозначным.
Для исправления ситуации удобно выбрать одну из девушек
(например, самую высокую или самую красивую) и считать, что
она всегда стоит в «начале» хоровода. В этом случае каждый
способ составить хоровод можно однозначно описать кортежем
(x1, . . . , x10), учитывающим порядок, в котором остальные девушки следуют за выбранной ведущей. По смыслу задачи этот кортеж
является перестановкой длины 10, и, следовательно, интересующее нас число способов P10 = 10! = 3 628 800.
Стоить также заметить, что в проделанных рассуждениях для
однозначного описания хоровода необходимо договориться, в каком направлении (по часовой стрелке или против) замыкается
«хвост» хоровода, однако выбор того или иного способа не сказывается на результате.
б. Найти число способов, которыми можно составить бусы из
11 разных камешков. В задаче предполагается, что камешки нанизаны на замкнутую нить, имеющую форму окружности.
Р е ш е н и е. На первый взгляд, эта задача полностью аналогична предыдущей, однако бусы в отличие от хоровода можно
перевернуть «вверх ногами» и у нас останутся те же самые бусы.
В контексте рассуждений предыдущей задачи это означает, что,
закручивая «хвост» хоровода по часовой стрелке и против, мы получаем разные хороводы, а в случае с бусами оба направления
6