Теорема 3. Число сочетаний без повторений

Теорема 2. Число перестановок с повторениями

Число r -перестановок с повторениями из n -множества равно .

# Следует из обобщённого правила произведения, где n ₁ =n, n₂=n, n₃=n, …, n_r=n. (Выбираем из исходного множества какой-либо элемент, ставим его на очередное место в перестановке, но из исходного множества не удаляем и его можно будет выбрать ещё раз) #

В перестановках с повторениями r может быть больше n, так как при выборе элемента мы не удаляем его из множества и можем выбрать еще раз.

Число r -сочетаний без повторений из n -множества равно

.

# Число r -перестановок без повторений из n -множества равно , однако порядок элементов в r ‑выборке здесь нас не интересует. Число возможных перестановок элементов в r -выборке равно . Следовательно, число сочетаний без повторений в r! раз меньше числа перестановок без повторений. #

Следствие 1.

Свойство симметричности для числа сочетаний без повторений: .

# #

Следствие 2. , т.к. (Ноль предметов выбрать из n предметов можно единственным способом – ничего не выбирать. Выбрать n предметов из n без учета порядка можно единственным способом – выбрать все n предметов.)

Следствие 3. При r>n (в сочетаниях с повторениями r не может быть больше n, так как мы не можем из n -множества забрать более, чем n элементов).

Числа являются коэффициентами бинома Ньютона (a+b) ⁿ:

Например, (a+b)³ = a ³ + 3 a ² b + 3 ab ² + b ³

.

Поэтому числа сочетаний без повторений еще называют биномиальными коэффициентами.

Ещё одно обозначение этих чисел: .

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