Простейшие конфигурации

2.1. Размещения с повторениями. Так называются упорядоченные r-выборки из (n)-множества.

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

1. 2 расстановки считаются различными, если они отличаются либо видом входящих в них предметов, либо порядком следования этих видов.

2. В каждую расстановку может входить несколько предметов одного вида.

Свойство. Число r-размещений с повторениями из предметов n типов обозначается и равно n^r.

Доказательство. На 1-м месте может быть предмет одного из n видов. Следовательно, существует n способов выбрать 1-й предмет. При каждом фиксированном таком способе имеется n способов выбрать 2-й предмет, и т.д. В соответствии с правилом произведения всю группу из r предметов можно выбрать n^r способами, что и требовалось доказать.

В примере 1.1.а) существует 12⁵» 250 тыс. различных паролей. (Если взломщик будет тратить по 1 секунде на проверку комбинации, то ему понадобиться 69 часов для проверки всех паролей).

Пример 1.3. В азбуке Морзе самый длинный код буквы состоит из 5 символов. Можно ли использовать коды длиной не более 4-х символов?

Решение. В соответствии с правилом суммы число различных кодов длиной не более 4 символов при использовании 2 видов символов (точка и тире) равно = 2 + 4 + 8 + 16 = 30. Значит, 4-х символьных кодов не хватит для кодирования даже всех букв кириллицы, не говоря о служебных символах. При использовании же 5-ти символьных кодов N = 30 + = 62, т.е. такой длины кода достаточно.

2.2. Размещения и перестановки без повторений. Размещениями без повторений называются упорядоченные r-выборки из n-множества. Такие расстановки по r элементов составляются из n неповторяющихся предметов.

Свойство. Число r-размещений без повторений из n предметов обозначается и равно n×(n – 1)…(n – r + 1) = .

Доказательство. 1-й предмет можно выбрать n способами, 2-й – (n – 1) способами, т.к. число кандидатов на это место уже n – 1, и т.д. В соответствии с правилом произведения получаем выражение из r сомножителей:

.

В примере 1.1.б) число способов выбора 4-х членов в руководство комитета из 25 человек равно = 25×24×23×22 = 303600.

В частном случае при r = n получаем = Р_n = n! Данная конфигурация называется перестановкой из n неповторяющихся предметов – упорядоченная n-выборка из n-множества.

2.3. Перестановки с повторениями. Так называют упорядоченные n-выборки из (m)-множества (n > m). Если некоторые элементы такой выборки совпадают, то могут существовать неразличимые (совпадающие) перестановки.

Найдем количество различных перестановок. Обозначим a, b,…, z – переставляемые объекты; n_j – количество повторений j-го элемента, j = 1,…,m, ; Р(n₁, n₂,…, n_m) – число таких перестановок. Рассмотрим 1-ю перестановку: .

Объекты “а” можно переставлять n₁! способами, но поскольку все они одинаковы, то такие перестановки не дают новых комбинаций. Следовательно, число действительно различных перестановок за счет совпадения первых n₁ элементов будет в n₁! раз меньше, чем в случае всех различающихся элементов. Аналогично, совпадение n₂ элементов “b” уменьшает число различных перестановок в n₂! раз, и т.д. Поскольку при несовпадении всех n элементов количество перестановок было бы равно n!, то

Р(n₁, n₂,…, n_m) = .

Пример 1.4. Найти все перестановки букв в слове “мама”.

Решение. В данном слове есть объекты 2-х типов – “м” и “а”. Всего множество содержит 4 элемента. Следовательно, число перестановок равно . Действительно, имеем следующие комбинации: ”аамм”, “мама”, “амам”, “ммаа”, “амма”, “маам”.

Пример 1.5. Найти число перестановок букв в слове “Миссисипи”.

Решение. Длина этого слова – 9 букв. Из них буква “м” встречается 1 раз, “и” – 4 раза, “с” – 3, “п” – 1. Следовательно, число перестановок равно

Р(1, 4, 3, 1) = = 2520.

2.4. Сочетания без повторений. Так называются неупорядоченные r-выборки из n-множества (r < n).

Свойство. Число r-сочетаний без повторений из n предметов обозначается и равно .

Доказательство. Каждое неупорядоченное r-сочетание можно упорядочить r! способами и получить r-размещение. Следовательно, сочетаний в r! раз меньше, чем размещений, т.е.

= Р(r, n – r).

В примере 1.1.в) 6 делегатов из 125 человек можно выбрать = 4.691×10 ⁹ способами

Пример 1.6. В лотерее из 36 номеров будут выбраны 5. Какова вероятность угадать ровно 3 номера из 5?

Решение. 3 номера из 5 верных можно выбрать способами. На каждый угаданный номер могут приходиться любые 2 из 31 невыбранных номеров, т.е. сочетаний. Окончательное число благоприятных случаев равно . Общее же число случаев равно количеству выпадения 5 номеров из 36, т.е. .

Отсюда вероятность угадывания равна » 0.0123 – немногим более 1%.

2.5. Сочетания с повторениями. Это неупорядоченные r-выборки из (n)-множества. Они получаются, например, если необходимо r неразличимых предметов разместить по n ящикам, в частности возможно n > r.

Свойство. Число r-сочетаний с повторениями из n предметов обозначается и равно .

Доказательство. Обозначим r_j ³ 0 – количество элементов j-го типа в сочетании, (r_j можно интерпретировать как количество предметов в j-м ящике). Набор значений r_j однозначно определяет текущее сочетание. Представим этот набор в виде следующей бинарной последовательности. Числа r_j отобразим в группы из r_j единиц, каждую такую группу отделим от соседних одним нулем (если r_j = 0, то несколько нулей могут стоять подряд). Число промежутков равно n – 1. Например, набор (2, 0, 3, 1), n = 4, r = 6 соответствует последовательности (1, 1, 0, 0, 1, 1, 1, 0, 1).

Построенная конструкция – не что иное, как набор перестановок с повторениями объектов 2-х видов – 0 и 1. Число нулей в этих сочетаниях равно n – 1, а единиц – r. Следовательно, , что и требовалось доказать.

Пример 1.7. Определить количество N возможных сочетаний из 8 пирожных 4-х сортов.

Решение. В данном случае r_j– число пирожных j-го сорта. Следовательно, r = 8, n = 4 и N = == 165.

Другой вариант доказательства основан на построении взаимно-однозначного отображения напрямую между элементами повторных и бесповторных сочетаний. Свяжем каждый набор r₁, r₂, …, r_n с элементами n – 1-сочетаний без повторений из множества чисел {1, 2,…, n + r – 1}. Обозначим К_j, j = 1,…, n –1– число, стоящее на j-м месте в отбираемом сочетании (К_j > К_j–1), формально положим К₀ = 0. Построим взаимно-однозначное отображение

f: (r₁, r₂, …, r_n) ® (K₁, K₂, …, K_n–1)

по следующему правилу:

r_j = К_j – К_{j – 1} – 1, j = 1,…, n – 1; (1.1)

r_n = (n + r – 1) – К_{n –1}.

Очевидно, обратное отображение строиться по формуле

К_j = , j = 1,…, n –1. (1.2)

Покажем, что числа, найденные по формулам (1.1) являются элементами r-сочетаний с повторениями. Действительно, т.к. при любом j и , то . Кроме того

.

Несложно также убедиться, что числа К_j, полученные по формуле (1.2) являются натуральными, и обладают всеми свойствами элементов сочетаний:

;

Следовательно, отображение f действительно устанавливает взаимно однозначное соответствие между элементами r-сочетания из (n)-множества и элементами n – 1-сочетания из n + r – 1-множества. Отсюда = = . Последнее равенство вытекает из формулы числа сочетаний.

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

1. =. Это свойство вытекает из формулы числа сочетаний.

2. = + .

Доказательство. Разобьем все r-сочетания на два класса. К первому классу отнесем сочетания, содержащие объект a_n, ко второму классу – не содержащие a_n. Так как в первом классе меняются только r – 1 элементов из n – 1 возможных, то он содержит r – 1-сочетания из n – 1-множества, следовательно, в нем элементов. Второй класс содержит все r-сочетания из n – 1-множества, т.к. в них нет одного элемента – a_n. Следовательно, в нем элементов. Общее число сочетаний, согласно правилу суммы равно + , что и требовалось доказать.

Данное свойство позволяет легко построить рекуррентный процесс вычисления всех чисел сочетаний. Положим по определению для любого n ³ 0 (ноль элементов из любого множества, в том числе – пустого, можно выбрать 1 способом, кроме того, по определению 0! = 1 – см. формулу из 2.4) и (отрицательное количество элементов выбрать невозможно). Организуем двойной цикл для вычисления всех , r £ m £ n:

for m:= 1 to n do

for r:= 0 to m do := +

Описанный процесс удобно представить в виде таблицы, называемой треугольником Паскаля:

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

…………………….

В таблице каждая m-я строка состоит из чисел , r = 0, … m, каждый элемент равен сумме двух элементов, расположенных над ним (пустое место считается нулем).

3.

Доказательство. Пусть имеем последовательность из n двоичных разрядов, содержащих 0 или 1. Очевидно, что каждую такую последовательность можно рассматривать, как n-размещение с повторениями из элементов 2-х типов, значит, количество этих размещений равно 2ⁿ.

Теперь рассмотрим некоторое множество из n объектов – а₁, … а_n, из которого будем образовывать все возможные сочетания без повторений, включая: 0-сочетания (не выбирается ни один объект), 1-сочетания и т.д., n-сочетания. При этом любую из упомянутых выше последовательностей из 0 и 1 можно интерпретировать, как перечень элементов, отбираемых в сочетание – если на k-м месте последовательности стоит 1 – элемент а_k отобран, если 0 – не отобран. Очевидно, что таким образом будут перечислены все бинарные n-последова-тельности. По правилу суммы общее число таких сочетаний, а, значит – и бинарных последовательностей равно Свойство доказано.

Замечание. Каждая отбираемая в сочетание группа элементов представляет собой некоторое подмножество исходного множества из n объектов. Следовательно, число всех подмножеств (включая пустое) множества из n элементов равно 2ⁿ.