СОЧЕТАНИЕ

СОЧЕТАНИЕ — одно из понятий комбинаторики (см.). Сочетание из n элементов по k называется всякое подмножество, состоящее из k элементов множества из n элементов. Два сочетания считаются различными, если некоторый элемент, входя в одно из них, не входит в другое. Число различных сочетаний из n элементов (некоторого n-элементного множества) по k (элементов) обозначается символом Сnk и выражается формулой:1837где Ank — число размещений из n элементов по k, Рk —число перестановок из k элементов. Числа Сnk являются биномиальными коэффициентами.

Пример. Сколько существует в выпуклом n-угольнике точек пересечения диагоналей, считая, что никакие три из них не пересекаются в одной точке?

Решение. Каждая искомая точка вполне определяется двумя диагоналями. Всякие две (пересекающиеся) диагонали вполне определяются четырьмя вершинами n-угольника — теми, которые они соединяют. Обратно, всякие четыре вершины n-угольника определяют одну из искомых точек. Поэтому ответом на задачу будет число сочетаний из n (вершин) по 4, т. е.:1838Франц. combinaison — сочетание.

Комментарии для сайта Cackle