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

Кортежи и а) различны, но имеют один и тот же состав — в оба кортежа входят три буквы а и две буквы Уточним понятие состава кортежа. Пусть а — кортеж длины составленный из элементов -множества Перенумеруем элементы множества Тогда каждому числу соответствует число показывающее, сколько раз элемент встречается среди компонент кортежа а. Выписывая по порядку эти числа, получаем новый кортеж который и называют составом кортежа а. Например, если то кортеж а имеет состав (3, 0, 2, 1).

Два кортежа, имеющие один и тот же состав, могут отличаться друг от друга лишь порядком компонент. Их называют перестановками с повторениями данного состава. Решим следующую комбинаторную задачу:

Найти число перестановок с повторениями у имеющих состав

Прежде чем решать эту задачу в общем виде, рассмотрим частный случай — найдем число перестановок с повторениями из букв Сначала перенумеруем эти буквы: Так как после нумерации все буквы стали различны (мы можем теперь отличить от то из них можно составить перестановок, где Если стереть в каждой из этих перестановок значки при буквах, то получатся перестановки с повторениями из букв а, а, Например, из перестановки получим При этом одна и та же перестановка с повторениями получается несколько раз. Например, перестановка с повторениями получается из всех перестановок букв в которых на первых трех местах стоят буквы (в любом порядке), на

четвертом и пятом месте — буквы любом порядке), а шестое и седьмое места занимают буквы и Но буквы можно переставлять способами, буквы способами и буквы способами. Поскольку эти способы можно произвольным образом комбинировать друг с другом, то получаем, что получается из перестановок букв Столькими же способами может получиться любая другая перестановка с повторениями букв а, а, Значит, число различных перестановок с повторениями в раз меньше общего числа перестановок семи букв равно

Точно так же разбирается общий случай: количество перестановок с повторениями, имеющих состав выражается формулой:

Например, буквы слова «Миссисипи» можно переставлять способами.

Из формулы (1) вытекает, что букв а и букв можно переставлять способами. Но это число равно . Значит, число перестановок с повторениями состава равно

Это утверждение можно вывести и не ссылаясь на общую формулу (1). В самом деле, любая перестановка с повторениями из букв а и букв однозначно определяется выбором мест, на которых стоят буквы Но общее число мест равно а буквы занимают мест, и эти места можно выбрать способами.

Отметим, что формулу бинома Ньютона можно доказать, воспользовавшись равенством (2). В самом деле, запишем выражение следующим образом:

А теперь раскроем скобки, выписывая множители в порядке их появления. Например, запишем в виде:

Ясно, что слагаемые в правой части будут всевозможными перестановками с повторениями длины из букв а и Чтобы привести подобные члены, нужно найти число перестановок, имеющих заданный состав. Но, как мы видели, число перестановок состава равно Поэтому слагаемое входит в сумму с коэффициентом . В результате получаем формулу бинома Ньютона:

Приведенное доказательство без изменений переносится на случай нескольких слагаемых. Рассуждая точно так же, как и выше, убеждаемся, что

где суммирование распространено на все кортежи такие, что

15. Сочетания с повторениями. В предыдущем пункте мы нашли число кортежей данного состава. Найдем теперь число различных составов, которые могут иметь кортежи длины состоящие из элементов -множества Каждый такой состав является кортежем, состоящим из чисел таких, что Его можно записать в виде кортежа из нулей и единиц, заменив каждое число соответствующим числом единиц и поставив нуль после каждой группы единиц, кроме последней. Например, вместо кортежа (4, 2, 1) можно написать (1, 1, 1, 1, 0, 1, 1, 0, 1), а вместо кортежа (2, 0, 0, 3) — кортеж (1, 1, 0, 0, 0, 1, 1, 1). Число единиц, входящих в полученные кортежи, равно а число нулей равно Поэтому число различных кортежей такого вида равно числу перестановок с повторениями из единиц и нулей, т. е. Но

Итак, мы доказали, что число составов кортежей длины , компоненты которых принадлежат данному -множеству, равно

Различные составы кортежей длины из элементов множества называют также сочетаниями с повторениями из элементов по

Их число обозначают

Мы доказали, что