2014-02-24
2456
Сочетания без повторений
Сочетания из n по m – набор из m элементов n -элементного масива, без учета порядка элементов в наборе.
Сочетание – произвольное (неупорядоченное) m -подмножество из n элементов.
Различные сочетания отличаются составом элементов, но не их порядком.
1) 
Þ 
;
;
; 
;
при m £ 0 и m ³n.
2) Симметричность числа сочетаний:
.
3) Правило Паскаля:
Для числа сочетаний из n по m справедливо следующее рекурентное cоотношение: 
.
4) Бином Ньютона:
При a = x = 1, 
, 
, k = 0,1… n - биноминальные коэффициенты.
Например:
A={1,2,3}
Сочетания из 3 по 2: {12, 31, 32}.
