Вход или регистрация

Сочетания в комбинаторике

В комбинаторике часто рассматривают задачи на отыскание количества подмножеств, содержащих по k элементов каждое, можно составить из m элементов данного множества Х?

Такие подмножества носят название сочетаний без повторений из элементов по k: C. Выведем формулу, выражающую C через m и k. Возьмем какое-нибудь k-подмножество А в m-множестве Х. Так как множество А содержит k элементов, то его можно упорядочить k! способами. При этом каждое упорядоченное k-множество, состоящее из элементов множества Х, может быть получено таким путем. Значит число упорядоченных k-множеств, составленных из элементов множества Х, в k! раз больше числа неупорядоченных k-подмножеств в Х.

Например, из элементов множества А = {a, b, c, d} можно составить четыре трехэлементных подмножества: {a, b, с}; {a, b, d}; {a, c, d}; {b, c, d}. Число же упорядоченных трехэлементных подмножеств в 3! = 6 раз больше:

{a, b, с}; {a, b, d}; {a, c, d}; {b, c, d}

{a, c, b}; {a, d, b}; {a, d, c}; {b, d, c}

{b, a, с}; {b, a, d}; {c, a, d}; {c, b, d}

{b, c, a}; {b, d, a}; {c, d, a}; {c, d, b}

{c, a, b}; {d, a, b}; {d, a, c}; {d, b, c}

{c, b, a}; {d, b, a}; {d, c, a}; {d, c, b}.

Но число упорядоченных k-множеств равно А, а число
k-подмножеств мы обозначили через C. Поэтому А= k! C. Так как А=,то мы получаем формулу, выражающую число k-подмножеств в m-множестве: C=

Если множество А состоит из m элементов, то его подмножества, содержащие k элементов, называются сочетаниями без повторений из m элементов по k элементов. Их число подсчитывают по формуле:

Пример. Сколькими способами можно выбрать делегацию в 5 человек из группы, содержащей 12 человек?

Поскольку порядок членов делегации не играет роли, то нам надо узнать, сколько можно выбрать пятиэлементных подмножеств из множества, содержащего 12 элементов. Число таких подмножеств С==792.

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

Решение: Имеем множество, состоящее из 12 элементов. Так как нам нужно определить количество партий, т.е. подмножеств, куда входят 2 элемента, то речь идет о сочетании без повторений из 12 элементов по 2 элементам. Это можно подсчитать следующим образом: С==66. Таким образом, будет сыграно 66 партий.

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

Решение: Нам дано множество из х элементов. Известно, что каждая партия – это подмножество, которое состоит из 2-х элементов. Всего таких подмножеств – 91. Значит можно составить уравнение: С=91.

Решим данное уравнение: С==91; =91. Сократим на (х – 2)!. Получим квадратное уравнение х– х=182, откуда х=14. Значит, в турнире участвовало 14 человек.

Рассмотрим более сложную задачу. В кондитерской продаются пирожные 4 сортов: наполеоны, безе, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Если записывать порядок, в котором продавец кладет пирожные в коробку, то получится кортеж длины 7 из 4 элементов – сортов пирожных. Однако два кортежа одного и того же состава, например (н, н, э, п, с, с, э) и (э, н, с, н, э, п, с), означают одну и ту же покупку: 2 наполеона, 2 эклера, 2 слоеных, 1 песочное. Поэтому два способа сделать покупку надо считать различными лишь в случае, когда соответствующие кортежи отличаются своим составом.

Итак, мы пришли к следующей задаче: сколько различных составов могут иметь кортежи длины k из m элементов? По-другому эту задачу можно сформулировать так: на сколько классов эквивалентности разбивается вся совокупность кортежей длины k из m элементов (назовем два кортежа эквивалентными, если они имеют одинаковый состав)? Такие классы эквивалентности называют сочетаниями с повторениями из m элементов по k, а их число обозначают С.

Сочетаниями с повторениями из m элементов по k вычисляют по следующей формуле.

С=

Вернемся к нашей задаче. В ней поставлен вопрос: сколько различных составов могут иметь кортежи длины 7, составленные из 4 элементов данного множества? По-другому эту задачу можно сформулировать и так: на сколько классов эквивалентности разбивается вся совокупность кортежей длины 7 из 4 элементов? В таком случае речь идет о сочетаниях с повторениями: С=C==120 (способов).

Рассмотрим свойства чисел С, которые выражают различные соотношения между подмножествами множества Х.

1. Если 0km, то верно равенство С= С. Докажем данное равенство, используя формулу сочетаний без повторений:

C=== С.

2. Для любых k и m, таких, что 0km, верно равенство С= С+ С.

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

С==;

С+ С=+=== С.

Отметим, что при k=0 получаем равенство С= С+ С. Так как С= С=1, то следует положить С=0. Аналогично С при k>m. Тогда доказанное выше равенство (2) оказывается верным и при k = m.

Данная формула позволяет вычислить значения С, зная С и С. Иными словами, с помощью этого тождества можно последовательно вычислить С сначала при m=0, затем при m=1, при m=2 и т.д. Вычисления удобно записывать в виде треугольной таблицы, которая получила название арифметического треугольника (или треугольника Паскаля):

1 1

1 2 1

1 3 3 1

1 4 6 4 1

………………………….

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

Доказанное свойство арифметического треугольника можно записать так:

С + С + С + … = С + С + С + …= С + С + С + … + С.

Из него следует, что сумма чисел (n + 1)-й строки вдвое больше суммы чисел n-й сроки. Иными словами, при переходе к следующей строке арифметического треугольника сумма чисел в строке удваивается. Но в первой строке стоит только одно число 1, а потому для этой строки сумма равна 1. Поэтому в (n + 1)-й сроке сумма чисел равна 2:

3. С + С + С + … + С = 2.

4. С– С = . С.

5. С+ С+ С= С.

6. С+ С+ С+ С = С.

7. С + С + С + … = 2.

8. С + С + С + … = 2.

Рассмотрим задачу. Пусть дано множество М={a, b, c, d}. Подсчитаем количество всевозможных подмножеств данного множества, состоящего из 4 элементов: одноэлементных подмножеств будет С==4; двухэлементных будет С==6; трехэлементных – С==4; четырехэлементных соответственно С==1 и еще одно пустое множество . Всего получилось 4+6+4+1+1=16 подмножеств, что соответствует 2=16.