3.2. Размещения без повторений

Решим задачу: имеется множество Х, состоящее из n элементов(n-множество). Сколько векторов длины k можно составить из элементов этого множества, если координаты вектора должны быть различными (не должны повторяться).

Число таких векторов (размещений без повторений из n элементов по k) будем обозначать . Будем рассуждать так: на первое место – имеем n претендентов. После того, как оно заполнено, на второе остается n-1 претендент, на третье – n - 2 претендента и т. д.

На k-ое место имеется n - (k - 1) кандидат(т. к. после того, как из n предложенных элементов уже выбрали k - 1, то остался n - (k - 1) =  n - k + 1 претендент на k-ое место). Применяя правило произведения, находим

.

Умножив числитель и знаменатель на (n-k) . . . 321, получим окончательный вид формулы:

.

Пример:

Сколько слов длины 4 можно составить из 33 букв русского алфавита, при условии, что все буквы различны.

.

3.3. Размещения с повторениями

Множества , из элементов, из которых составляются вектора, в правиле произведения могут иметь общие элементы. В частности, все они могут совпадать с одним и тем же множеством Х, содержащим n элементов.

Вектора длины k, составленные из элементов n - множества Х называют размещениями с повторениями (словами длины k в алфавите Х), а их число обозначают .

Из правила произведения сразу вытекает, что

k раз

Пример:

Сколько слов длины 6 можно составить из 26 букв английского алфавита?

.

3.4. Перестановки без повторений

Решим задачу: сколькими способами можно переставить между собой (поменять местами) сразу все k элементов множества Х?

Число - перестановок без повторений из n элементов – это число способов, сколькими по n местам можно расставить n элементов. Оно легко получается из формулы для размещений без повторений при условии, что длина создаваемых векторов k равна мощности всего множества n

.

0! по определению равен 1.

3.5. Перестановки с повторениями

Решим задачу: четыре цифры 1, 2, 3, 4 можно переставлять друг с другом способами. В слове “мама” - 4 буквы. Но перестановок из этих букв можно составить не 24, а только 6:

мама, маам, ммаа, амам, аамм, амма.

Чтобы понять, как это случилось, поставим в соответствие цифрам 1, 2 букву “м”, а 3 и 4 - “а”. Тогда, например, перестановке 1234 - “ммаа”, а 1324 - “мама”. Но слово “ммаа” соответствует не только перестановке 1234, но и 2134, 1243, 2143. Если цифры 1 и 2 меняются местами, то в соответствующем слове меняются местами две буквы “м” , следовательно, само слово остается неизменным. Таким образом, среди 24 перестановок 4 - х букв будут одинаковыми 2! тех, которые отличаются лишь сменой мест букв “м”, а также 2! тех, которые отличаются лишь переменой букв “а”. И тогда это число их:

.

Пусть дан вектор длины n, составленный из элементов , причем входит в вектор раз, - раза, . . . , - раз. Тогда

.

Если переставлять в этом векторе буквы, будут получаться новые векторы, имеющие тот же состав, т. е. буква входит раз и т. д. Будем называть эти векторы перестановками с повторениями и букв , имеющими состав . Обозначим . По правилу произведения число перемещений букв, не меняющих данную перестановку, равно Но n элементов можно переставлять друг с другом n! способами. Поэтому число различных перестановок букв, имеющих состав , в раз меньше, чем n! . Таким образом:

,

где .