Материал: erovenko_va_osnovy_vysshei_matematiki_dlia_filologov

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

Есть в опыте больших поэтов Черты естественности той, Что невозможно, их изведав, Не кончить полной немотой.

Размещение с повторениями термин достаточно явный и удобный. В случае «сочетаний с повторениями» с ясностью не все благополучно. Хотя если перестановки и размещения могут быть с повторениями, имеет смысл поговорить и о сочетаниях с повторениями. Такое название связано с классом задач, типичным представителем которых является следующая модельная задача о наборе пирожных.

Пример. В магазине продаются пирожные 4 сортов: бисквитные, песочные, слоеные и эклеры. Рассмотрим, сколькими способами можно составить набор из 8 пирожных.

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

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

На первый взгляд неясно, при чем тут сочетания. Математики знают, что пока задача не формализована, первый взгляд часто обман-

чив. Поэтому перейдем сразу ко второму, направив его на 8 пирожных, обозначенных «кружками», отделенными вертикальными палочками, т. е. «разделителями» (или «перегородками»), на соответствующей графической иллюстрации (рис. 2.3), указывающей конкретный способ набора пирожных.

Рис. 2.3

Символически разделители означают, что выбрано 2 бисквитных пирожных, 1 песочное, 3 слоеных и 2 эклера. Три разделителя делят пирожные на четыре группы по соответствующим сортам. Заметим, что в

112

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

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

n = 4, m = 8, заметим, что m ≥ n, то полученный результат способов набора из n сортов пирожных m пирожных, когда каждый сорт встречается

хотя бы один раз, можно записать в виде Cnm−−11 .

Вариант II. Пирожные не так хороши, как показалось вначале. До-

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

Теперь возможны любые расположения 8 кружков и 3 разделителей в графической иллюстрации, использованной выше. Рассмотрим, например, их расположение, отвечающее случаю (рис. 2.4), когда в наборе пирожных 3 бисквитных, ни одного песочного, 5 слоеных и ни одного эклера.

Рис. 2.4

В рассматриваемом варианте нет ограничений на расположение разделителей, они могут стоять на любых трех местах из 8 + 3 = 11 мест, занимаемых 8 кружками и 3 разделителями. В этой «модели» задачи надо выбрать 3 места для разделителей из 11 мест или 8 мест для кружков из 11 мест, т. е. способов выбора пирожных столько же, сколько существует 3-элементных подмножеств в 11-элементном множестве. Это число

ченный результат произвольных способов набора из n сортов пирожных

m пирожных можно записать в виде Cmn−+1n−1 =Cmm+n−1 .

Таким образом, мы получили формулу для способов выбора m объектов из n типов объектов с неограниченным повторением. Такие выборки принято называть «сочетания с повторениями».

Определение сочетаний с повторениями. Группы, составленные из m объектов, которые принадлежат одному из n типов элементов,

называют сочетаниями с повторениями.

113

Число всевозможных сочетаний с повторениями, а именно выборов m объектов из повторяющихся n элементов, обозначают символом Cnm .

С помощью горизонтальной черты над буквой C отличают случай с по-

вторениями от обычных сочетаний. Читается: «Число сочетаний из эн по эм» или «Цэ с чертой из эн по эм». Для нахождения числа Cnm сочетаний

с повторениями из n элементов по m приходится проявить определенную изобретательность.

Утверждение. Число сочетаний с повторениями Cnm можно вычислить по формуле:

Доказательство. Пронумеруем элементы исходного множества числами от 1 до n. Пусть в одно из сочетаний с повторениями вошло m1 элементов под номером 1, m2 элементов под номером 2, …, mn элементов под номером n. Поскольку составляются группы m из объектов, то ясно,

что m1 + m2 + … + mn = m.

Изобразим это сочетание с повторениями в виде последовательности чисел из 1 и 0. Единица будет обозначать каждый отдельный объект сочетания, а нуль — символическую «границу» между соседними группами. Если, например, некоторое mi = 0, т. е. элементов под номером i в сочетании нет, то в соответствующем месте последовательности окажется два «граничных» нуля подряд. Например, для n = 4 и m = 8, как в предыдущем примере, последовательность 11100111110 означает, что в этом сочетании 3 элемента под номером 1, ни одного элемента под номером 2, 5 элементов под номером 3 и ни одного элемента под номером 4. Поскольку сумма всех mi равна m, то в построенной последовательности содержится m единиц, а так как различных по составу элементов групп n, то нулей n – 1. Верно обратное: каждой такой последовательности соответствует сочетание с определенными повторениями.

Таким образом, задача свелась к поиску ответа на вопрос: сколько различных последовательностей длиной m+n–1 можно составить из m единиц и n–1 нулей? Это число перестановок с повторениями из

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

114

Заметим, что в предыдущем модельном примере вместо единиц мы рисовали кружки, а вместо нулей разделители, т. е. вертикальные чер-

точки. Рассмотрим модельную задачу о голосовании.

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

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

A37 = 37 = 2187 возможных исходов голосования.

Если нас не интересует, кто и как голосовал, а только общий результат голосования или, например, голосование тайное, то тогда речь идет о сочетаниях с повторениями. В этом случае подсчитывается число всевозможных сочетаний m = 7 голосований членов комитета из повторяющихся n = 3 видов голосования: «за», «против», «воздержался»,

исходов голосования.

Замечание. Сочетания с повторениями и размещения с повторениями объединяет то, что нет никаких ограничений на число повторений элементов, кроме общего их числа в наборе, поэтому в формуле чис-

Например, так было в задаче о «наборе пирожных» и в задаче о «голосовании». Но может быть и наоборот, т. е. в Cnm , m < n или m = n. На-

пример, «костяшки» домино можно рассматривать как сочетания с повторениями из 7 по 2 цифры 0, 1, 2, 3, 4, 5, 6. Их число равно

т. е. в домино всего 28 различных «костяшек».

Замечание. Сочетания (с повторениями или без) отличаются от размещений (с повторениями или без) прежде всего тем, что первые — неупорядоченные наборы, а вторые — упорядоченные.

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

4 = 1+1+1+1 = 1+2+1 = 1+1+2 = 2+1+1 = 2+2 = 1+3 = 3+1.

115

Сколькими способами можно представить произвольное натуральное число m в виде суммы из n натуральных слагаемых? Эта задача сводится к решению уравнения в целых неотрицательных числах.

Пример. Посчитаем, сколько решений в целых неотрицательных числах для натурального числа m имеет уравнение:

x1 + x2 + … + xn = m, где xi ≥ 0, i = 1, 2, …, n.

Воспользуемся подсказкой древнегреческого математика Диофанта Александрийского. Одна из его книг начинается фразой: «Ты, конечно,

знаешь, что каждое целое есть просто некоторое количество единиц».

Как и при доказательстве формулы числа сочетаний с повторениями, изобразим число m в виде последовательности m единиц и расставим n–1 нулей, обозначающих «границу» между соседними n группами единиц, в каждой из которых содержится некоторое натуральное число единиц xi, i = 1, 2, …, n. Заметим, что если единиц в некоторой группе нет, то соответствующее число единиц xi = 0. Поэтому число решений в целых неотрицательных числах заданного уравнения равно числу сочета-

Алгебраические уравнения с целыми коэффициентами, у которых ищутся решения в целых числах, называются диофантовы уравнения по имени Диофанта, изучавшего такие уравнения. Мы нашли число решений диофантова уравнения x1 + x2 + … + xn = m при предположении xi ≥ 0. Число решений этого уравнения при предположении xi >0 (заметим, что тогда m ≥ n)находится, как и в случае варианта I модельного примера о

«наборе пирожных», по формуле Cmn−−11 .

Рассмотрим еще раз модельную задачу о «наборе пирожных», переформулировав ее в виде следующей задачи о дележе монет.

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

Вариант I — пираты с признаками морали, т. е. допускается любой способ дележа монет, при котором каждый пират получает хотя бы одну монету. Воспользовавшись графической иллюстрацией на рис. 2.3, где «кружки» — это монеты, разделенные «перегородками», указывающими конкретный способ дележа монет среди пиратов, а именно первому пирату — 2 монеты, второму — 1 монету, третьему — 3 монеты и четвертому — 2 монеты, получим с помощью аналогичных рассуждений, что

116