Лекция 07. Элементы комбинаторики
.docЛекция 7. Элементы комбинаторики.
Комбинаторика – это раздел математики, изучающий количество комбинаций, которые можно составить из заданного конечного множества попарно различных элементов произвольной природы.
Одно из важных правил комбинаторики – правило умножения:
если объект А может быть выбран из множества Mn h способами и при каждом выборе объекта А другой объект В может быть выбран k способами, то объект , состоящий из двух объектов А и В может быть выбран hk способами.
Конечные подмножества элементов множества Mn называются соединениями.
Если в совокупности соединений подмножества образованы только попарно различными элементами множества Mn, то такие соединения называются соединениями без повторений.
Если в совокупности соединений входят подмножества не только с попарно различными элементами множества Mn, но и с одинаковыми, то такие соединения называются соединениями с повторениями.
Различают три основных типа соединений: размещения, перестановки, сочетания.
Определение 7.1. Размещением из n элементов по m элементов без повторений называется упорядоченное подмножество попарно различных m элементов множества Mn ().
Определение 7.2. Перестановкой из n элементов без повторений называется упорядоченное множество всех n элементов множества Mn, то есть перестановка без повторений – это размещение без повторений из n по n элементов.
Определение 7.3. Сочетанием из n элементов по m элементов без повторений называется подмножество из m попарно различных элементов множества Mn без учёта порядка их следования ().
Для размещения или сочетания с повторениями требуется лишь условие, что и, следовательно, m может быть любым натуральным числом, независимым от числа n элементов множества Mn.
В перестановке с повторениями присутствуют все элементы множества Mn, причём указывается, сколько раз повторяются элементы . Число элементов в такой перестановке может быть любым натуральным числом, большим или равным n.
Обозначим символами , , число всех размещений, сочетаний без повторений из n элементов по m элементов и число всех перестановок без повторений из n элементов (). Символы для обозначения числа всех соединений определённого типа берутся из начальных букв соответствующих французских слов: arrangement – размещение, combination – комбинация, сочетание, permutation – перестановка.
Символами , , обозначим число всех размещений, сочетаний, перестановок с повторениями (m, mi – любые натуральные числа). Число mi указывает, что элемент ai повторяется в перестановке mi раз, причем .
Произведение n первых натуральных чисел обозначается символом n! и называется n-факториалом: .
☼ По определению 0!=1 и =1. ☼
♦ Теорема 7.1. Число размещений без повторений из n элементов по m элементов вычисляется по формуле
, (7.1)
число размещений из n элементов по m элементов с повторениями
. (7.2)
Доказательство. Докажем методом математической индукции формулы (7.1) и (7.2).
1) Для m=1 они справедливы, так как выбор по одному элементу из множества Mn можно осуществить только n способами, а по формулам (7.1) и (7.2) , .
2) Пусть эти формулы справедливы для произвольного фиксированного натурального числа k, то есть , . По правилу умножения , , так как в случае подмножества с попарно различными элементами множества Mn после выбора k элементов из Mn в нём останется n–k элементов, из которых по одному элементу можно выбрать n–k способами. А в случае размещения с повторениями (k+1)‑м элементом может быть любой из n элементов множества Mn. Учитывая, что , убеждаемся в справедливости формул (7.1) и (7.2). ■
Следствие 1. Так как , то . Таким образом, получается формула числа перестановок:
(7.3)
Формула для перестановок с повторениями такова:
. (7.3а)
Справедливость этой формулы установим следующими рассуждениями: если бы в перестановке все элементов были попарно различными, то таких перестановок было бы . Но, меняя между собой одинаковый элемент ai любыми mi! способами, мы не изменяем самой перестановки. Поэтому в знаменатель надо внести произведение факториалов .
Следствие 2. По правилу умножения . Следовательно,
,
то есть справедлива формула
. (7.4)
♦ Теорема 7.2. Число сочетаний из n элементов по m элементов с повторениями вычисляется по формуле
. (7.5)
Доказательство. Докажем формулу (7.5) методом математической индукции.
1) Для m=1 она справедлива, так как , а выбор по одному элементу из множества Mn можно осуществить только n способами.
2) Пусть формула (7.5) верна для произвольного фиксированного , то есть . Тогда, по правилу умножения, , т.к. вставить один элемент, взятый из Mn, мы можем n+k способами, добавив к уже выбранным k элементам либо один из них, либо любой из Mn. А в знаменателе число 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. При любом справедливо равенство (бином Ньютона1)
. (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) – великий английский физик, механик, математик и астроном.