Неупорядоченная выборка без возврата. Сочетания, их свойства. Формула бинома Ньютона, Треугольник Паскаля. Определение числа всех подмножест

Неупорядоченной выборкой объёмом r на n-элементном множестве M называется совокупность (просто множество) r элементов из множества M необязательно различимых.

Кратность - число появлений каждого элемента.

При кратности = 1, т.е. при выборке без возврата, неупорядоченная выборка является r-элементным подмножеством мн. M и называется его сочетанием из n по r.

Число таких сочетаний: C^r_n=(ⁿ_r)

В общем случае число упорядоченных выборок = A^r_nсреди них имеются размещения, содержащие одни и те же элементы, различающиеся только порядком их расположения.

Любую совокупность элементов можно переставить P_rc n-ми. Поэтому, если не учитывать порядок расположения, то число сочетаний будет в P_rраз меньше, чем число размещений.

Число сочетаний - C^r_n=A^r_n/ P_r= n! / (n − r)! r!

Свойства числа сочетаний:

C^r_n= 0, если r >n
C⁰_n= Cⁿ_n= 1
C^r_n= C^r_n-1+C^r-1_n-1
C^r_n= C^n-r_n

Бином Ньютона:

Числа называются биномиальными коэффициентами.

Геометрическая интерпретация 3го свойства C^r_n= C^r_n-1+C^r-1_n-1

С помощью диаграмы треугольник Паскаля

Их можно вычислить, применяя только сложение, если пользоваться следующей схемой. В верхней строке пишем две единицы. Все последующие строки начинаются и заканчиваются единицей. Промежуточные числа в этих строках получаются суммированием соседних чисел из предыдущей строки. Эта схема называется треугольником Паскаля: