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

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

Предположим, что из чисел 3, 5, 7 необходимо составить различные произведения двух чисел. Таких произведений только три, а именно: . Это объясняется тем, что произведения вида и совпадают, так как порядок сомножителей, входящих в произведение, не учитывается. Если требуется из указанных цифр составить двузначные числа, то таких чисел уже шесть. Запишем эти числа: 35, 53, 37, 73, 57, 75. Как видно, здесь уже пришлось учитывать порядок цифр.

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

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

Пример. Пусть имеется множество, содержащее четыре буквы: {А, В, С, D}. Запишем все возможные сочетания из указанных букв по три. Таких сочетаний будет четыре: ABC; ACD; ABD; BCD. Здесь в числе сочетаний не включены, например, АСВ, ВСА, так как эти последовательности букв не отличаются от последовательности АВС, поскольку порядок элементов в сочетаниях не учитывается.

Число сочетаний из п различных элементов по т будем обозначать символомом , где . Иногда это число обозначают символом .

Прежде чем найти общую формулу для определения числа сочетаний, решим следующую задачу.