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

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

Пусть имеется элементов, среди которых – одинаковых предметов первого сорта; одинаковых предметов второго сорта;…, одинаковых предметов k-го сорта; и .

Число перестановок с повторениями из такого набора обычно обозначается .

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

Поэтому число различных перестановок с повторениями из элементов равно