Соединения без повторений

В этом разделе будут рассмотрены три вида соединений без повторений: размещения, перестановки и сочетания. Ради краткости добавку «без повторений» будем опускать.

1. Размещения.Размещения из n элементов по – это упорядоченные наборы из попарно различных элементов -множества . Таким образом, два размещения из элементов по различаются либо порядком, либо составом входящих в них элементов. Например, размещения из 3-множества по 2 исчерпываются следующими упорядоченными парами:

, , , , , .

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

Т е о р е м а 1.Число размещений из элементов по находится по формуле

= . (1)

Напомним, что произведение первых n натуральных чисел, т.е. , называют n-факториалом и обозначают . Произведение можно записать в виде дроби = и поэтому формулу (1) можно переписать следующим образом

= . (2)

В частности, при из формулы (2) получаем

= = 1.

Это означает, что существует единственный упорядоченный набор длины 0 – пустой кортеж, не имеющий ни одной компоненты.

Пример 1.Найти число пятизначных чисел в десятичной системе счисления, в записи которых цифры не повторяются.

□ Рассуждая по аналогии с тем, как это делалось при рассмотрении примера 1 (2-й способ) из § 2, приходим к выводу, что искомое число есть .

2. Перестановки.Рассмотримтеперь различные линейные упорядочения данного -множества . Получаемые при этом упорядоченные наборы отличаются друг от друга лишь порядком входящих в них элементов. Их называют перестановками (без повторений) из n элементов, а их число обозначают через . Например, если , то = 6, так как из трех элементов можно составить шесть перестановок:

, , , , , .

Общая формула для получается из формулы (1), поскольку перестановка из элементов – это то же самое, что размещение без повторений из элементов по . Полагая в (1) получим = = = = . Итак, справедлива

Т е о р е м а 2.Число перестановок из элементов равно -факториал, т.е.

= . (3)

Полагая в формуле (2) , получаем

= . (4)

Сравнивая (3) и (4), приходим к выводу, что 0! = 1. На первый взгляд это равенство кажется парадоксальным. Но для всех справедливо равенство = . Если потребовать, чтобы это равенство было справедливо и при , то получим . Отсюда вновь следует, что естественно положить0! = 1.

Пример 2.Сколькимиспособамиможно расположить на полке 7 различных учебников так, чтобы «Алгебра» и «Геометрия» не стояли рядом?

□ Условимся указанные учебники обозначать для краткости буквами А и Г соответственно. Число всевозможных способов расстановки учебников равно числу перестановок из семи элементов, т.е. . Но при этом сосчитаны и те, в которых встречаются рядом учебники А и Г, причем в двух позициях: АГ и ГА. Считая АГ и ГА за одну книгу, для каждого такого расположения получим расстановок, в которых учебники А и Г встречаются рядом. Искомое число расстановок учебников равно .

3. Сочетания.Одной из важнейших задач комбинаторики является подсчет числа k-подмножеств данного n-множества . Такие неупорядоченные подмножества называются сочетаниями из элементов по , а их число обозначают через (от французского слова combinaison – сочетание). Например, из элементов 4-множества можно составить следующие 2-множества: , , , , , . Число этих подмножеств равно 6. Следовательно, = 6. Отметим, что = 1, так как каждое множество имеет лишь одно 0-множество, а именно, пустое множество . Далее понятно, что = , поскольку в ‑множества содержится одноэлементных подмножеств. Ясно также, что .

Выведем формулу, выражающую через и . Для этого укажем способ получения всех размещений из элементов по . Выберем любое k-подмножество данного n-множества . Это можно сделать способами. Каждое такое k-подмножество упорядочим всевозможными способами. Таких различных упорядочений столько, сколько можно составить перестановок из элементов, т.е. = . Понятно, что таким способом получатся все размещений из элементов по . Значит, имеет место равенство = . Отсюда вытекает справедливость следующего утверждения.

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

= = = . (5)

Пример 3.Найти число всех диагоналей правильного n-угольника.

□ Любые две вершины n-угольника однозначно определяют отрезок, соединяющие эти вершины. Поэтому число всевозможных отрезков, соединяющих вершины n-угольника, равно числу сочетаний из по 2, т.е. . Но среди них находятся и сторон n-угольника, которые диагоналями не являются,

Таким образом, искомое число равно

.

Например, при получаем, что правильный 10-угольник имеет = 35 диагоналей.

Свойства сочетаний.

. = .

□ В самом деле, в силу формулы (5) имеем

= = = .

. = .

□ Действительно,

= = = .

. + = .

□ В самом деле,

+ = + = = = = .

. + + ….+ + … + = .

□ Действительно, сумма + + ….+ + … + равна числу всех подмножеств -множества, а по теореме 5 из § 2 это число равно .

4. Треугольник Паскаля.Для вычисления числа сочетаний удобно пользоваться таблицей, имеющую форму треугольника, в n‑й строке (n=0,1,2,…) которой выписываются сочетания , , …., :

. . . . . . . . .

….

. . . . . . . . . . .

Таблица 1.

Такую треугольную таблицу называют треугольником Паскаля по имени французского математика Блэза Паскаля (1623­‑1666), в трудах которого она встречается. Это название исторически неточно, так как такую таблицу знали уже арабские математики Гиясэддин Каши и Омар Хайям, жившие в XIII веке, а из европейских ученых с ней был знаком итальянский математик Николо Тарталья (1550‑1557).

Непосредственно свойств ‑ сочетаний вытекают следующие