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

Из элементов множества X = {7, 4, 5} можно образовывать не только кортежи различной длины, но и различные подмножества, например двухэлементные. В комбинаторике их называют сочетания­ми без повторений из трех элементов по два элемента.

Определение. Сочетание без повторения из k элементов по т эле­ментов – это т-элементное подмножество множества, содер­ жащего k элементов.

Два сочетания из k элементов по т элементов отличаются друг от друга хотя бы одним элементом.

Число всевозможных сочетаний без повторений из k элементов по т элементов обозначают . Как находить это число?

Обратимся сначала к примеру. Образуем различные двухэлементные подмножества из элементов множества Х ={7, 4, 5}. Их будет три: {7, 4}, {7, 5}, {4, 5}. Из элементов каждого такого подмножества можно обра­зовать 2! кортежей длины 2:

(7,4) (7,5) (4,5)

(4,7) (5,7) (5,4)

Все полученные кортежи являются размещениями без повторений из трех элементов по два и их число равно = 3^.2 = 6. Но, с другой стороны, это число равно произведению 2!^.. Значит, = 2! ^. , откуда =.

В общем виде: ==.

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

Дата добавления: 2014-01-06