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

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

Теорема: .

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

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

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

Теорема доказана. Разумеется, это доказательство имеет смысл только в случае, когда n > m.