Лекция 07. Элементы комбинаторики

Лекция 7. Элементы комбинаторики.

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

Одно из важных правил комбинаторики – правило умножения:

если объект А может быть выбран из множества M_n h способами и при каждом выборе объекта А другой объект В может быть выбран k способами, то объект , состоящий из двух объектов А и В может быть выбран hk способами.

Конечные подмножества элементов множества M_n называются соединениями.

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

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

Различают три основных типа соединений: размещения, перестановки, сочетания.

Определение 7.1. Размещением из n элементов по m элементов без повторений называется упорядоченное подмножество попарно различных m элементов множества M_n ().

Определение 7.2. Перестановкой из n элементов без повторений называется упорядоченное множество всех n элементов множества M_n, то есть перестановка без повторений – это размещение без повторений из n по n элементов.

Определение 7.3. Сочетанием из n элементов по m элементов без повторений называется подмножество из m попарно различных элементов множества M_n без учёта порядка их следования ().

Для размещения или сочетания с повторениями требуется лишь условие, что и, следовательно, m может быть любым натуральным числом, независимым от числа n элементов множества M_n.

В перестановке с повторениями присутствуют все элементы множества M_n, причём указывается, сколько раз повторяются элементы . Число элементов в такой перестановке может быть любым натуральным числом, большим или равным n.

Обозначим символами , , число всех размещений, сочетаний без повторений из n элементов по m элементов и число всех перестановок без повторений из n элементов (). Символы для обозначения числа всех соединений определённого типа берутся из начальных букв соответствующих французских слов: arrangement – размещение, combination – комбинация, сочетание, permutation – перестановка.

Символами , , обозначим число всех размещений, сочетаний, перестановок с повторениями (m, m_i – любые натуральные числа). Число m_i указывает, что элемент a_i повторяется в перестановке m_i раз, причем .

Произведение n первых натуральных чисел обозначается символом n! и называется n-факториалом: .

☼ По определению 0!=1 и =1. ☼

♦ Теорема 7.1. Число размещений без повторений из n элементов по m элементов вычисляется по формуле

, (7.1)

число размещений из n элементов по m элементов с повторениями

. (7.2)

Доказательство. Докажем методом математической индукции формулы (7.1) и (7.2).

1) Для m=1 они справедливы, так как выбор по одному элементу из множества M_n можно осуществить только n способами, а по формулам (7.1) и (7.2) , .

2) Пусть эти формулы справедливы для произвольного фиксированного натурального числа k, то есть , . По правилу умножения , , так как в случае подмножества с попарно различными элементами множества M_n после выбора k элементов из M_n в нём останется n–k элементов, из которых по одному элементу можно выбрать n–k способами. А в случае размещения с повторениями (k+1)‑м элементом может быть любой из n элементов множества M_n. Учитывая, что , убеждаемся в справедливости формул (7.1) и (7.2). ■

Следствие 1. Так как , то . Таким образом, получается формула числа перестановок:

(7.3)

Формула для перестановок с повторениями такова:

. (7.3а)

Справедливость этой формулы установим следующими рассуждениями: если бы в перестановке все элементов были попарно различными, то таких перестановок было бы . Но, меняя между собой одинаковый элемент a_i любыми m_i! способами, мы не изменяем самой перестановки. Поэтому в знаменатель надо внести произведение факториалов .

Следствие 2. По правилу умножения . Следовательно,

,

то есть справедлива формула

. (7.4)

♦ Теорема 7.2. Число сочетаний из n элементов по m элементов с повторениями вычисляется по формуле

. (7.5)

Доказательство. Докажем формулу (7.5) методом математической индукции.

1) Для m=1 она справедлива, так как , а выбор по одному элементу из множества M_n можно осуществить только n способами.

2) Пусть формула (7.5) верна для произвольного фиксированного , то есть . Тогда, по правилу умножения, , т.к. вставить один элемент, взятый из M_n, мы можем n+k способами, добавив к уже выбранным k элементам либо один из них, либо любой из M_n. А в знаменателе число k+1 означает, что вставить этот дополнительный элемент, не изменяя сочетания, мы можем либо вначале, либо между первым и вторым и т.д., либо после последнего (то есть k+1 вариантов).

Учитывая, что , убеждаемся, что формула (7.5) справедлива для m=k+1, а значит, она справедлива и для любого натурального числа m. ■

♦ Теорема 7.3. Справедливо правило симметрии

. (7.6)

Доказательство. . ■

♦ Теорема 7.4. Справедлива формула (правило Паскаля)

. (7.7)

Доказательство.

. ■

♦ Теорема 7.5. Число всех подмножеств из n элементов равно :

.

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

1) При n=1 имеем множество одного элемента , которое содержит два подмножества: пустое множество и само себя.

2) Пусть установлено, что множество из k элементов содержит ровно подмножеств.

Рассмотрим множество из k+1 элементов. Любое его подмножество В получается одним из двух способов:

а) берётся подмножество В множества ,

в) берётся подмножество и присоединяется элемент .

Каждым из этих способов получаем подмножеств, а всего подмножеств множества А. ■

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

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

Решение. По формуле (7.2) (размещения с повторениями) находим: . 

 Пример 7.2. Сколько неподобных членов содержится в многочлене

Решение. По формуле (7.5) (сочетания с повторениями) находим:



 Пример 7.3. Сколькими способами можно составить футбольную команду, если её формируют из трёх вратарей и пятнадцати полевых игроков?

Решение. Так как полевых игроков в команде 10 и всего 1 вратарь, то по правилу умножения . 

 Пример 7.4. Сколько слов, без учёта их смысла, можно составить из букв слова «длинношеее»?

Решение. По формуле (7.3а) (перестановки с повторениями) находим:

. 

 Пример 7.5. Сколько четырёхзначных чисел можно составить из цифр 0, 1, 5?

Решение. Так как число не начинается с нуля, то из числа надо вычесть число :

. 

 Пример 7.6. Сколько шестизначных телефонных номеров можно установить?

Решение. По формуле (7.2) (размещения с повторениями) находим:

. 

♦ Теорема 7.6. При любом справедливо равенство (бином Ньютона¹)

. (7.8)

Доказательство. Формулу (7.8) докажем методом математической индукции.

1) Проверяем верность формулы при n=1: , так как по формуле (7.4) , . Таким образом, при n=1 формула (7.8) верна.

2) Предположим, что формула (7.8) верна для некоторого n. Докажем, что при n+1 имеет место такая же формула, то есть что

. (7.9)

В самом деле,

.

В силу того, что , , , , , следует формула (7.9). Из 1) и 2) на основании метода математической индукции заключаем, что формула (7.8) верна для любого натурального числа n. ■

Формулу (7.8) обычно коротко записывают так: .

При n=2 и n=3 получаем хорошо знакомые формулы:

;

.

1 Ньютон Исаак (1642-1727) – великий английский физик, механик, математик и астроном.

33