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

Размещениями с повторением из n элементов по m называются комбинаторные соединения, представляющие собой слова длины m в алфавите объемом n, различающиеся либо самими буквами, либо их порядком.

Пусть А = {a₁, a₂,..., a_n) - конечный алфавит, состоящий из n букв, и пусть - число слов в алфавите А, имеющих длину m, буквы в которых могут повторяться. Например, возможно слово а₁⁽^m), т.е. содержащее одну единственную букву. Возможны любые произвольные сочетания, включающие вхождения некоторых букв произвольное число раз и в произвольном порядке.

Теорема = n^m.

Доказательство Докажем теорему методом математической индукции по m.

1. Базис: При m =1 число Q(1) различных слов, которые могут быть образованы в алфавите А, равно его мощности, т.е. n. Следовательно, Q(1)= = n¹=n. Базис индукции доказан.

2. Индукционное предположение: пусть для некоторого m доказано, что Q(m)= = n^m. Определим число слов в длины m+1 при этом предположении. Все слова длины m+1 можно получить, приписывая справа к каждому слову длины m какую-нибудь букву алфавита. Очевидно, каждое слово длины m можно дополнить n способами, т.е. общее число слов длины m+1 окажется в n раз больше числа слов длины m. Следовательно, Q(m+1)=Q(m)*n= n*n^m=n^m⁺¹= .