§ 4. Соединения с повторениями

Если рассмотреть теперь снова задачи, разобранные в §§ 1 и 2, то мы увидим, что решение почти всех из них не требует уже никаких рассуждений, а получается непосредственным применением нужной формулы из выведенных в предыдущем параграфе. Собственно говоря, все рассуждения, которые приводились при решении задач, были не чем иным, как именно выводом соответствующей формулы, но только для данного конкретного случая. Формулы § 3 потому и являются общими, что они применимы ко всем соединениям

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

Однако в числе приведенных там примеров есть и такие, которые не укладываются в уже рассмотренные схемы. К ним относятся, скажем, примеры 1 и 5 из § 1. Дело в том, что при определении различных видов соединений в предыдущем параграфе мы брали некоторое определенное множество, элементы которого существовали «в единственном экземпляре» и в каждое данное соединение могли входить только один раз. Между тем в некоторых случаях элементы в соединении могут повторяться, как например ноты в музыкальной фразе в примере 5 из § 1. Для того чтобы охватить общей теорией и такие задачи, необходимо рассмотреть соединения с повторениями, которым и посвящен настоящий параграф.

Пусть имеется непересекающихся множеств каждое из которых содержит не менее чем элементов. Для простоты мы будем называть элементы множества элементами 1-го сорта, элементы множества — элементами 2-го сорта, элементы множества — элементами m-го сорта. Иначе говоря, мы рассматриваем разбиение (см. п. 7 Введения) некоторого множества на непересекающиеся подмножества состоящие из элементов различных «сортов». Все элементы каждого подмножества, то есть элементы одного и того же сорта, будем считать одинаковыми, или совпадающими между собой.

Слова «одинаковые» или «совпадающие» употребляются здесь в том смысле, в каком одинаковыми являются, например, 12 белых или 12 черных шашек. Именно в таком смысле понимается распространенное выражение «множество с повторяющимися элементами», хотя оно и не согласуется с описанным во Введении пониманием терминов «множество» и «элемент» (согласно которому множества, содержащие одни и те же элементы, считаются совпадающими).

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

Из элементов множества А, то есть элементов, входящих в различные его подмножества можно составлять различные упорядоченные множества, содержащие по элементов в каждом. Такие упорядоченные множества принято называть размещениями с повторениями из элементов сортов по элементов, или, более коротко, просто размещениями с повторениями из элементов по

В первом из этих терминов (более точном, но менее употребительном из-за своей громоздкости) явным образом указывается, что имеется не различных элементов, а различных сортов элементов; число же элементов любого сорта в размещении может быть каким угодно.

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

Размещения с повторениями можно рассматривать и в случае то есть неравенство которое считалось необходимым в предыдущем параграфе, здесь необходимым уже не является. Например, из элемента можно образовать размещения по элемента. Они будут иметь вид:

Число различных возможных размещений с повторениями из элементов по элементов будем обозначать

Теорема 1. Число различных размещений с повторениями из элементов по элементов определяется по формуле:

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

Проведем теперь доказательство формулы (1) по индукции. Ясно, что при число размещений равно

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

и найдем число размещений с повторениями из элементов по . Пользуясь формулой (2), получаем:

Таким образом, формула (1) справедлива для и из ее справедливости для некоторого следует и справедливость для Теорема доказана.

Упражнения

(см. скан)

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

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

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

Занумеруем сначала все элементы а номерами буквы — номерами и будем считать все эти элементы различными. Тогда мы имеем множество, состоящее из

различных элементов, и число перестановок этого множества, в силу теоремы 2 предыдущего параграфа, равно причем

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

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

Следовательно, в числе перестановок всех элементов каждая считается раз. Отсюда следует, что число различных перестановок с повторениями в нашем случае равно

Обозначая число перестановок через , мы можем сформулировать полученный результат в виде следующей теоремы.

Теорема 2. Число различных перестановок из элементов, в которых элементы повторяются соответственно раз, выражается формулой

Упражнения

(см. скан)

Определение 3. Сочетанием с повторениями из элементов по элементов называется всякое множество, содержащее элементов, каждый из которых является элементом одного из данных сортов.

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

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

Из тех же трех элементов сочетания с повторениями по три элемента будут следующими:

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

Число различных возможных сочетаний с повторениями из элементов по элементов мы будем обозначать символом Г. Для его нахождения можно воспользоваться следующей теоремой.

Теорема 3. Число различных возможных сочетаний с повторениями из элементов по элементов может быть найдено по формуле

Доказательство. Как уже говорилось выше, сочетания, в том числе с повторениями, являются неупорядоченными множествами. Поэтому всякое сочетание однозначно определяется тем, сколько элементов каждого сорта в него входит.

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

Такое сочетание можно условно записать комбинацией четырех чисел (2, 4, 0, 1), показывающей, сколько элементов каждого сорта берется.

Другие сочетания определятся, например, комбинациями (3, 0, 0, 4) или (1, 1,2, 3). Первая из них определяет сочетание, состоящее из трех элементов первого сорта и четырех элементов четвертого. Элементы второго и третьего сорта в это сочетание не входят. Вторая комбинация определяет сочетание, содержащее один элемент первого сорта, один — второго, два — третьего и три элемента четвертого сорта. Заметим еще, что, пока мы рассматриваем сочетания из четырех элементов по семи, условная запись представляет комбинацию всегда четырех чисел — по одному числу на каждый имеющийся сорт элементов, и сумма этих чисел всегда равна семи, то есть общему числу элементов, входящих в сочетание.

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

Такую комбинацию мы будем записывать в виде

Комбинацию определяющую сочетание, можно записать, пользуясь только цифрами 1 и 0. Сделаем это следующим образом. Вместо числа означающего количество элементов первого сорта в сочетании, напишем такое же число единиц. Затем таким же способом запишем число элементов второго сорта, а между этими двумя группами единиц поставим нуль для их разделения. Так же будем поступать и дальше. Комбинация (1, 1, 2, 3) изобразится тогда как (1010110111), а комбинация (2, 1, 2, 2) — как (1101011011). Запись (1011011101) соответствует комбинации (1, 2, 3, 1).

Если какое-либо из чисел равно нулю, то есть элементы данного сорта в сочетание не входят, то единиц на этом месте писать не будем, и два или несколько нулей могут тогда оказаться рядом. Например, комбинация (2, 4, 0, 1) запишется в виде (1101111001). Запись (1111000111) соответствует комбинации (4, 0, 0, 3).

Запись из нулей и единиц, соответствующая сочетанию из элементов по элементов, будет содержать ровно единиц и нулей. Действительно, количество единиц равно числу элементов в сочетании, а количество нулей на единицу меньше числа сортов

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

Теорема доказана.

Если сравнить полученное выражение с формулой (7) для числа сочетаний без повторений, выведенной в предыдущем параграфе, то мы заметим, что

Таким образом, число сочетаний с повторениями из элементов по элементов равно числу сочетаний без повторений из элементов по элементов.

Упражнения