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

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

Рождение комбинаторики как раздела математики связано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну
из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.

В дальнейшем важную роль будет играть следующая

Лемма. Пусть в множестве Am элементов, а в множестве Bn элементов. Тогда число всех различных пар (a,b), где ain A,bin B будет равно mn.

Доказательство. Действительно, с одним элементом из множества A мы можем составить n таких различных пар, а всего в множестве Am элементов.

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

Пусть у нас есть множество из трех элементов left{ a,b,cright}. Какими способами мы можем выбрать из этих элементов два? ab,ac,bc,ba,ca,cb.

Определение. Размещениями множества из n различных элементов по m элементов (mle n) называются комбинации, которые составлены из данных n элементов по m> элементов и отличаются либо самими элементами, либо порядком элементов.

Число всех размещений множества из n элементов по m элементов обозначается через {sf A}_m^n (от начальной буквы французского слова “arrangement”, что означает размещение), где n=1,2,ldots и m=overline{1,n}.

Теорема. Число размещений множества из n элементов по m элементов равно

    [{sf A}_n^m=n(n-1)dots(n-m+1).]

Доказательство. Пусть у нас есть элементы a_1,a_2,ldots,a_n. Пусть a_{i_1},a_{i_2},ldots,a_{im} — возможные размещения. Будем строить эти размещения последовательно. Сначала определим a_{i_1} — первый элемент размещения. Из данной совокупности n элементов его можно выбрать n различными способами. После выбора первого элемента a_{i_1} для второго элемента a_{i_2} остается n-1 способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

    [{sf A}_n^m=n(n-1)cdotdotscdot(n-m+1).]

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

Решение. Искомое число трехполосных флагов:

    [{sf A}_5^3=5cdot4cdot3=60.]

Определение. Перестановкой множества из n элементов называется расположение элементов в определенном порядке.

Так, все различные перестановки множества из трех элементов { a,b,c} — это

    [abc,acb,bac,bca,cab,cba.]

Очевидно, перестановки можно считать частным случаем размещений при m=n>.

Число всех перестановок из n элементов обозначается {sf P}_n (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

    [{sf P}_n=n(n-1)cdotldotscdot2cdot1=n!]

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

Решение. Искомое число расстановки 8 ладей

    [{sf P}_8=8!=40320.]

Rendered by QuickLaTeX.com

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

Определение. Сочетаниями из n различных элементов по k элементов называются комбинации, которые составлены из данных n элементов по k элементов и отличаются хотя бы одним элементом (иначе говоря, k-элементные подмножества данного множества из n элементов).

Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из n элементов по k элементов в каждом обозначается {sf C}_n^k (от начальной буквы французского слова “combinasion”, что значит “сочетание”).

Числа {sf C}_n^k

{sf C}_5^{2}=10

Все сочетания из множества { a,b,c,d,e} по два — ab,ac,ad,ae,bc,bd,be,cd,ce,de.

{sf C}_n^0=1,{sf C}_n^n=1,{sf C}_n^1=n.

Свойства чисел {sf C}_n^k

1. {sf C}_n^k={sf C}_n^{n-k}.

Действительно, каждому k-элементному подмножеству данного n-элементного множества соответствует одно и только одно n-k-элементное подмножество того же множества.

2. {sf C}_n^k={sf C}_{n-1}^k+{sf C}_{n-1}^{k-1}.

Действительно, мы можем выбирать подмножества из k элементов следующим образом: фиксируем один элемент; число k-элементных подмножеств, содержащих этот элемент, равно {sf C}_{n-1}^{k-1}; число k-элементных подмножеств, не содержащих этот элемент, равно {sf C}_{n-1}^k.

Треугольник Паскаля

Rendered by QuickLaTeX.com

В этом треугольнике крайние числа в каждой строке равны 1, а каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним. Таким образом, этот треугольник позволяет вычислять числа {sf C}_n^k.

Rendered by QuickLaTeX.com

{sf C}_7^3=35;{sf C}_8^6=28.

Теорема.

    [{sf C}_n^k={n!over k!(n-k)!}qquad (0le kle n)]

Доказательство. Рассмотрим множество из n элементов и решим двумя способами следующую задачу: сколько можно составить последовательностей из k элементов данного
множества, в каждой из которых никакой элемент не встречается дважды?

1 способ. Выбираем первый член последовательности, затем второй, третий и т.д. член

    [n(n-1)(n-2)ldots(n-k+1).]

2 способ. Выберем сначала k элементов из данного множества, а затем расположим их в некотором порядке

    [{sf C}_n^kcdot k!,]

    [{sf C}_n^kcdot k!=n(n-1)dots(n-k+1),]

    [{sf C}_n^k={n(n-1)(n-2)dots(n-k+1)over k!}.]

Домножим числитель и знаменатель этой дроби на (n-k)!:

    [{sf C}_n^k={n!over k!(n-k)!}.]

    [displaystyle {sf C}_{20}^8={20cdot19cdot18cdot17cdot16cdot15cdot14cdot13over 1cdot2cdot3cdot4cdot5cdot6cdot7cdot8}=323cdot390=125970.]

Пример. Сколькими способами можно в игре “Спортлото” выбрать 5 номеров из 36?

Искомое число способов

    [{sf C}_{36}^5={36!over 5!31!}={36cdot35cdot34cdot33cdot32over 1cdot2cdot3cdot4cdot5}=376992.]

Задачи.

1. Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?
2. На рояле 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков?
3. Сколько есть шестизначных чисел, делящихся на 5?
4. Сколькими способами можно разложить 7 разных монет в три кармана?
5. Сколько можно составить пятизначных чисел, в десятичной записи которых хотя бы один раз встречается цифра 5?
6. Сколькими способами можно усадить 20 человек за круглым столом, считая способы одинаковыми, если их можно получить один из другого движением по кругу?
7. Сколько есть пятизначных чисел, делящихся на 5, в записи которых нет одинаковых цифр?
8. На клетчатой бумаге со стороной клетки 1 см нарисована окружность радиуса 100 см, не проходящая через вершины клеток и не касающаяся сторон клеток. Сколько клеток может пересекать эта окружность?
9. Сколькими способами можно расставить в ряд числа 1, 2, ldots, n так, чтобы числа 1, 2, 3 стояли рядом и притом шли в порядке возрастания?
10. Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 5, 7, 8, если каждую цифру можно использовать только один раз?
11. Из слова РОТ перестановкой букв можно получить еще такие слова: ТОР, ОРТ, ОТР, ТРО, РТО. Их называют анаграммами. Сколько анаграмм можно составить из слова ЛОГАРИФМ?
12. Назовем разбиением натурального числа представление его в виде суммы натуральных чисел. Вот, например, все разбиения числа 4:

    [4;3+1;1+3;2+2;2+1+1;1+2+1;1+1+2;1+1+1+1.]

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

Сколько существует различных разбиений числа 11 на 4 слагаемых?
13. Сколько существует трехзначных чисел с невозрастающим порядком цифр?
14. Сколько существует четырехзначных чисел с невозрастающим порядком цифр?
15. Сколькими способами можно рассадить в ряд 17 человек, чтобы A и B оказались рядом?
16. n девочек и n мальчиков рассаживаются произвольным образом в ряду из 2n мест. Сколькими способами можно их рассадить так, чтобы никакие две девочки не сидели рядом?
17. n девочек и n мальчиков рассаживаются произвольным образом в ряду из 2n мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?

Ссылка на основную публикацию