Сочетания без повторений

Термин «сочетание» в его современном значении начал первым употреблять Б. Паскаль. Обозначение C введено в 1880 году первоначально в виде С . Второе, принятое в настоящее время обозначение введено Л. Эйлером.

При составлении k – элементных подмножеств n –элементного множества нас не интересует порядок, в котором располагаются элементы.

Например, если имеется 10 сортов ткани и нужно выбрать 4 сорта, то порядок, в котором будут выбраны сорта, не имеет значения. В таких задачах речь идёт о подмножествах, не являющихся упорядоченными.

Определение. Всякое k- элементное подмножество n -элементного множества (k n) называют сочетанием без повторений из n элементов по k.

Число различных сочетаний из n элементов по k обозначают символом C .

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

Теорема 8. Число сочетаний и з n элементов по k элементов определяется по формуле:C = .

ÿ Формула для числа сочетаний легко получается из формул для числа размещений и числа перестановок. Действительно, составив сначала все сочетания из n элементов по k, а затем, переставив всеми возможными способами элементы, входящие в каждое сочетание, получим все размещения из n –элементов по k–элементов. Но из каждого такого сочетания можно составить k! перестановок. То есть справедлива формула:

k! C =A C = = .

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

Задача. Из группы студентов, состоящей из 25 человек, надо составить команду из 4 человек для участия в беге на 1000 м. Сколькими способами можно это сделать?

Решение. Порядок следования элементов в данном соединении значения не имеет. Из 25 человек набрать команду из 4 человек можно:

С = =12650 (способами).

Ответ: 12650 способов.

Вспомним теорему о том, что конечное множество, содержащее п элементов, имеет 2 ^п подмножеств, то есть если А_п={а₁,а₂,...,a_п }, то п(Р(А_п))=2^п.

Напомним также, что принято считать 0! равным 1.

При этом предположении формула С = остаётся в силе и при k=n, и при k =0 и поэтому имеет равенство:

=2 .

Свойства чисел C

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

а) ;

б) ;

в) ;

г) .

д) Правило симметрии.

Если 0 k n, то верно равенство: C =C .

 Известно, что C = .

Найдём C = = = .

Следовательно, C =C .

Утверждение доказано.

е) Для k,n: 0 k n, верно равенство:

(n + 1) C =(k + 1) C .

(n + 1) C = = ;

(k + 1) C = = = = = .

Следовательно, (n + 1) C =(k + 1) C .

Утверждение доказано.

ж) Правило Паскаля.

k, n: 0 k n верно равенство: C =C + C .

Найдем C :

C = = = ;

Найдем C : C = = = .

Найдём C + C :

C + C = + = =

= = = C .

з) Для любого m верны равенства:

C + C + … + C =2 ;

C – C + C – C +…+ (– 1) C + … + (–1) C =0;

C + C + C + …=C + C + C + …=2 .

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

Задача 1. Некоторый комитет состоит из 12 человек. Минимальный кворум для принятия решения должен насчитывать 8 человек. а) Сколькими способами может быть достигнут минимальный кворум? б) Сколькими способами может быть достигнут какой-либо кворум?

Решение. а) Искомое число совпадает с С и равно:

С =С =С = =495 (способа)

б) Какой-либо кворум достигается, если на заседании присутствует 8, 9, 10, 11 или 12 членов комитета. Согласно правилу суммы искомое число равно:

C + C + C + C + C =C + C + C + C + C =

=495 + + + + 1=794 (способа)

(При вычислении мы учли, что 0!=1, и поэтому C =1).

Ответ: а) 495 способов; б) 794 способа.

Задача 2. У 6 взрослых и 11 детей обнаружены признаки инфекционного заболевания. Сколькими способами можно взять выборочный анализ, чтоб изучить течение болезни у 2 взрослых и 3 детей.

Решение. Из 6 взрослых выбрать двух можно:

C = =15 (способами)

Из 11 детей выбрать трёх можно:

С = =165 (способами)

Согласно правилу произведения имеется 15 ∙ 165=2 475 способов выбора двух взрослых и трёх детей.

Ответ: 2 475 способов.