Материал: erovenko_va_osnovy_vysshei_matematiki_dlia_filologov

После индексации букв слова БАОБАБ, в котором 3 буквы Б, 2 буквы А и 1 буква О, получим 6=3+2+1 различных букв Б1, А1, О1, Б2, А2, Б3. Из них можно составить P6 = 6! различных 6-буквенных слов, т. е. перестановок из 6 различных букв. Это вспомогательный перечень.

Не трогая остальных букв и меняя местами лишь три буквы Б всеми возможными способами, а их будет по числу перестановок из трех букв Б1, Б2, Б3 всего 3!, получим вроде бы новые перестановки, но без индексации букв они будут неразличимы. Поэтому общее число перестановок уменьшится в 3! раз. Аналогичные рассуждения верны и для двух букв А, и лишь буква О одна. В итоге количество анаграмм слова БАОБАБ, без учета повторов слов, пересчитанных с помощью комбинаторного принципа умно-

жения, окажется равным числу 3!6!2! = 60. Чтобы не нарушать единообра-

зия поделим указанное выражение на 1! = 1, соответствующее числу перестановок одной буквы О в указанных анаграммах, поскольку полученное

число анаграмм принято записыватьвобщем виде 3!62!!1! = 60.

Для того чтобы частный случай подсчета анаграмм не стал, как сказал бы Козьма Прутков «пустою забавою», рассмотрим эту задачу в более общей постановке.

Определение перестановок с повторениями. Слова, составленные из n букв, которые можно получить из повторяющихся n1 букв а1, n2 букв а2, …, nk букв аk , где n1 + n2 + … + nk = n, называют перестановка-

ми с повторениями.

Число всевозможных перестановок с повторениями, а именно выборов n объектов с n1, n2, …, nk повторяющимися элементами, где n1 + n2 + … + nk = n, обозначают Pn1 ,n2 ,...,nk . С помощью горизонтальной черты над буквой P отличают случай с повторениями от обычных перестановок. Читается: «Число перестановок с повторениями из эн-один, эн-два и т. д. до эн-ка» или «Пэ с чертой из эн-один, эн-два и до эн-ка».

Утверждение. Число перестановок с повторениями Pn1 ,n2 ,...,nk , где n1 + n2 + … + nk = n, можно вычислить по формуле

Доказательство. Воспользуемся рассуждением, проведенным выше с использованием приема растождествления, который переносится на общий случай практически без изменений. Сначала предположим, что

97

все n объектов различны. Если это так, то имеется n! способов переставить или упорядочить его элементы. Заметим, что ni объектов для каждого i =1, 2, …, k является неразличимыми. Поэтому и способы расположения таких объектов, при которых остальные объекты остаются на своих местах, неразличимы. Поскольку имеется всего ni! для каждого i =1, 2, …, k таких расположений, то для нахождения общего количества различных перестановок с повторениями, когда все ni объектов для каждого i являются неразличимыми, необходимо n! разделить на ni! для каждого i =1, 2, …, k. В результате получим следующее число:

что и требовалось доказать.

В частности, из доказанного утверждения следует, что эта дробь всегда является целым числом. С помощью формулы числа перестановок с повторениями число анаграмм слова БАОБАБ, подсчитанное выше,

можно записать в виде P 3,2,1 = 6! = 60. Другой пример: число ана-

3! 2!1!

грамм слова ФИЛОЛОГИЯ, составленного из 9 букв, а именно 1-й буквы Ф, 2 букв И, 2 букв Л, 2 букв О, 1-й буквы Г и 1-й буквы Я, равно

P 1,2,2,2,1,1 = 9! = 45 360.

1! 2! 2! 2!1!1!

Заметим также, что в силу принятого соглашения 0! = 1 в формуле числа перестановок с повторениями Pn1,n2 ,...,nk , где n1 + n2 + … + nk = n, некоторые ni ≥ 0 могут быть равны 0. Например, если n1 = 3, n2 = 0, n3 = 2,

то n = 3 + 0 + 2 = 5 и P 3,0,2 = 5! = 10.

3! 0! 2!

Пример. Предположим, что, не поверив Соловью, горе-музыканты из «Квартета» решили создать вместо квартета камерный оркестр. Для этого Мартышка привела с собой еще трех таких же Мартышек, Осёл — еще двух Ослов, а Козёл — еще одного Козла и лишь Мишка поленился и остался в одиночестве. Рассмотрим, сколькими способами можно рассадить их в один ряд.

Музыкантов стало 4 + 3 + 2 + 1 = 10, из них 4 Мартышки, 3 Осла, 2 Козла и 1 Мишка. Полагая n1 = 4, n2 = 3, n3 = 2, n4 = 1 и n = 10, по фор-

муле для числа перестановок с повторениями получим

Вариантов много, но заиграет ли когда-нибудь такой оркестр?

98

мое an–mbm входит в правую часть с коэффициентом Cnm . Таким образом,

получаем искомую формулу бинома Ньютона:

(a + b)n = P0,n an + P1,n−1an–1b +…+ Pm,n−m an–mbm +…+ Pn−1,1abn–1+ Pn,0 bn = = Cn0 an + Cn1 an–1b + … +Cnm an–mbm + … + Cnn−1 abn–1 + Cnn bn.

Заметим, что, делая повторяющиеся объекты неразличимыми, мы игнорируем их порядок, как это было в сочетаниях, поэтому можно получить аналог равенства для перестановок с повторениями и сочетаний в

Действительно, пусть имеется совокупность из n объектов, в которую входит n1 неразличимых объектов 1-го типа, n2 неразличимых объектов 2-го типа и вообще ni неразличимых объектов i-го типа для i =1, 2, …, k. Рассмотрим, как можно заполнить n мест объектами задан-

ной совокупности. Существует Cnn1 способов выбрать места для n1 неразличимых объектов 1-го типа. Если эти все места выбраны, то для заполнения остается n–n1 мест, поэтому имеется Cnn−2 n1 способов выбрать

места для n2 неразличимых объектов 2-го типа. Если места для объектов 1-го и 2-го типов выбраны, то для заполнения останется n–n1–n2 мест,

а это и есть число способов перестановок с повторениями.

100

Это удивительно: хотя мы не рассматривали никаких перестановок, тем не менее выведена формула, повторяющая формулу для числа перестановок с повторе-

ниями. Дело в том, что поставленную задачу о подсчете вариантов можно трактовать двояко. Например, попытаемся ответить на следующий вопрос: сколькими способами n студентов можно распределить по k мероприятиям так, чтобы на первом мероприятии оказалось n1 студентов, на втором — n2 студентов и т. д., где n1 + n2 + … + nk = n ? С одной стороны, мы распределяем отличающихся друг от друга студентов по разным мероприятиям. В этой трактовке задачи получаются сочетания. С другой стороны, если бы мы распределяли среди студентов, например, n билетов на k мероприятий, причем сами билеты были бы неотличимы друг от друга, то в такой интерпретации задачи получаются перестановки с повторениями билетов на одно и то же мероприятие, предназначенных для n студентов.

Анаграммы, т. е. комбинации фиксированного числа букв, естест-

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

(a1 + a2 + … + ak)n = ∑ Pn1 ,n2 ,...,nk a1n1 a2n2 ... aknk ,

где суммирование распространено на все наборы (n1, n2, …, nk), для ко-

торых n1 + n2 + … + nk = n и n1 ≥ 0, n2 ≥ 0, …, nk ≥ 0.

Замечание. Коэффициент при a1n1 a2n2 ... aknk , получающийся при возведении в n-ю степень суммы из k слагаемых a1+a2+…+ak (здесь n = n1 + n2 + … + nk и ni ≥ 0, для i =1, 2, …, k), равен числу анаграмм сло-

aini = ai0 = 1, т. е. буква ai в соответствующем одночлене отсутствует, и,

кроме того, напомним, что ni! = 0! = 1 в формуле для коэффициента при таком одночлене.

Например, если для n = 3, k = 3 аккуратно перемножить (a + b + c) три раза на себя получится формула вида

(a + b + c)3 = (a + b + c)(a + b + c)(a + b + c) =

= a3 + b3 + c3 + 3(a2b + a2c + b2a + b2c + c2a + c2b) + 6abc.

Коэффициенты 1, 3 и 6 — это известные нам количества анаграмм.

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

либо степень буквы. Одночлен a3 получается только одним способом

P 3,0,0 = 3!/(3!0!0!) = 1, аналогично b3 — P 0,3,0 = 3!/(0!3!0!) = 1 и c3 —

P 0,0,3 = 3!/(0!0!3!) = 1. Одночлену a2b соответствуют aab, aba, baa, т. е.

101