double arrow

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


Перестановкой с повторениями называется размещение с повторениями по n из n элементов k-множества M (k£n) со следующим дополнительным условием: различные k элементов множества M повторяются соответственно n1,…,nk раз, 1£n1,…,nk£n, n1+…+nk=n.

Теорема 6. Число перестановок с повторениями различных k элементов n1,…,nk раз, 1£n1,…,nk£n, n1+…+nk=n, равно .

Доказательство. Пусть M – множество номеров перестановки с повторениями, одной из указанных в условии теоремы, M1,…,Mk – множества номеров с одинаковыми элементами, повторяющимися n1,…,nk раз соответственно. Тогда семейство множеств {M1,…,Mk} будет разбиением множества M на k блоков. Значит, каждой перестановке с повторениями соответствует вполне определенное разбиение множества M на k блоков. Ясно, что это соответствие является биекцией. Значит, искомое число перестановок с повторениями равно числу разбиений на k блоков .

Задача 3. Найти число всех перестановок букв слова «баобаб».

Решение. n1=3 (буква «б»), n2=2 ( «а»), n1=1 («о»), значит, .



Сейчас читают про: