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

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

.

# Пусть дано n -множество S и T_i – n_i -подмножества множества S, где i =1,2,…, n. Тогда доказательство есть частный случай применения обобщенного правила произведения, где

n ₁ =n, n₂=n- 1, n₃=n- 2, …, n_r=n-r+ 1 #

Следствие 1. Число перестановок n предметов равно:

.

Следствие 2. .

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

По определению, (ноль предметов можно выбрать из n предметов единственным способом – ничего не выбирать).

 

1. Выборка. Виды выборок. Примеры. Упорядоченные выборки. Теоремы о числе упорядоченных выборок с повторениями. Доказательства. Следствия.

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

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

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

 

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

 

1. Выборка. Виды выборок. Примеры. Неупорядоченные выборки. Теоремы о числе неупорядоченных выборок без повторений. Доказательства. Следствия.

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

Число 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 ³

.

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

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