Сочетания. Пусть опыт состоит в выборе k элементов без возвращения и без упорядочения из некоторого множества, содержащего n элементов

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

Сочетаниями из n элементов по k называется любое подмножество из k элементов, которые принадлежат множеству, состоящему из n различных элементов.

Например, при выборе делегации в составе 3 человек из 30 студентов, очевидно, не надо учитывать порядок выбранных делегатов, т.к. все члены делегации равноправны. Поэтому каждый такой выбор будет сочетанием из 30 по 3. Однако, выбирая старосту, профорга и физорга из тех же студентов, порядок уже приходится учитывать. В этом случае каждый конкретный результат будет уже размещением из 30 по 3.

Найдем число возможных сочетаний С _n^k. Чтобы получить размещение из n элементов по k, а их число равно A _n^k, надо выбрать k элементов из множества, содержащего n элементов, что можно сделать C _n^k способами, и организовать из них упорядоченное подмножество. Последнюю операцию можно выполнить P _n способами. Таким образом, чтобы получить A _n^k размещений, надо выполнить две операции, которые можно осуществить С _n^k и Р _n способами, соответственно. Поэтому, согласно принципу умножения, можно записать

. (1.3)

Отсюда получаем

. (1.4)

Заметим, что С _n⁰= C _nⁿ =1, C _n ¹= n.

Пример 1.9. Сколькими способами можно составить комиссию в составе из трех человек из имеющихся 9 человек, 4 женщин и 5 мужчин, если: а) не важен пол членов комиссии; б) комиссия должна состоять из двух женщин и одного мужчины.

Решение. а) Из смысла задачи следует, что порядок выбора членов комиссии не играет роли. Здесь важен только состав. Тогда выбрать комиссию из трех человек из 9 имеющихся можно

способами.

б) Двух женщин из 4 имеющихся можно выбрать С₄² способами, а одного мужчину из 5 можно С₅¹ способами. тогда общее количество способов выбора комиссии, в соответствии с принципом умножения, можно

способами.

Отметим, что при использовании сочетаний могут быть полезны следующие свойства:

1⁰. (свойство симметрии),

2⁰. ,

3⁰. (свойство Паскаля).