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

Пусть в множестве A имеются одинаковые (повторяющиеся) элементы. Перестановкой с повторениями состава (n₁, n₂, … ,n_k) из элементов (a₁, a₂, … ,a_k) называется кортеж длиной n = n₁ + n₂ + …+ n_k, в который a₁ входит n₁ раз, a₂ входит n₂ раз и т.д. Число таких перестановок

Пример.

Сколько слов можно получить, переставляя буквы в слове «МАТЕМАТИКА»

Решение

Слово «МАТЕМАТИКА» является кортежем длины 10, имеющим состав (2, 3, 2, 1, 1, 1) т.е. буква «М» входит два раза, буква «А» входит 3 раза, буква «Т» входит два раза, а остальные по одному разу. Число слов при перестановке букв слова «МАТЕМАТИКА» будет равно

 

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

Каждое взаимно однозначное отображение f: X —> Y называется перестановкой множества X.

Если т = п, то каждая взаимно однозначная функция f: X —> Y является взаимно однозначным отображением множества X на множество Y. В таком случае [п]_п = п (п-1) (п-2) . . . 1 обозначаем п! (п факториал).

Теорема. Число перестановок n-элементного множества равно п!.

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

 

Справочные зависимости.

|т|_п = (т- п+1) |т|_п-1