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

Определение. Отображение множества первых натуральных чисел в данное множество , называется размещением с повторениями, составленным из данных элементов по .

Размещения с повторениями называются также конечными последовательностями.

Два размещения с повторениями одинаковы тогда и только тогда, когда на одинаковых местах находятся одни и те же элементы.

Если в размещении с повторениями некоторый элемент ставится в соответствие различным натуральным числам, т.е., иначе говоря, данный элемент занимает различных мест, то говорят, что этот элемент повторяется в размещении раз.

Пример. Всевозможные размещения с повторениями из трех элементов по 2:

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

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

Предположим, что число размещений с повторениями из элементов по равно . Составим из данных элементов всевозможные размещения с повторениями по элементу. Во всяком размещении с повторениями по элементу

первые элементов

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