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

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

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

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

k раз

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

.

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

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

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

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

.

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

.

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

.