Теорема 4. Число сочетаний с повторениями

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

.

# 1 способ – доказательство Эйлера.

Пусть дано n -множество S. Пронумеруем все его элементы, т.е. множеству S взаимно однозначно поставим в соответствие множество S’: S «S’ ={1, …, n } – номера элементов из S. Тогда r -выборке из S однозначно соответствует выборка r натуральных чисел из S’. Т.к. в сочетании порядок не важен, r -выборку натуральных чисел можно расположить так, чтобы

a ₁ £ a ₂£ … £ a_r (1)

(где a_i – выбранное натуральное число). Между числами стоит знак £, т.к. выборка с повторениями и числа могут повторяться (например, а₂ и а₃ могут быть одним и тем же числом).

Добавим в выборке (1) к а₁ ноль, к а₂ – 1, к а₃ – 2 и т.д., т.е. получим выборку

a ₁+0 < a ₂+1 < … < a_r+r -1 (2)

Выборка (2) взаимно однозначно соответствует выборке (1), причём в ней нет одинаковых чисел (неравенство строгое). Следовательно, выборка (2) – это r -выборка без повторений из множества S’’` ={1, …, n, n +1, n +2, …, n+r -1}, S’’ - (n+r -1)-множество.

Таким образом, Эйлер свёл задачу о числе r -сочетаний с повторениями из n -множества к числу r -сочетаний без повторений из (n+r -1)-множества.

1. Комбинаторные задачи о покрытиях, укладках, разбиениях. Примеры. Теорема о числе разбиений элементов множества на 2,3,…,k классов, без учета их порядка в классах и без ограничений на занятость класса. Доказательства. Следствия (класс – то же, что и ящик).

Число упорядоченных (r1,r2,…,rk) – разбиений n-множества равно Pn(r1,r2,…,rk):

.

По теореме о числе сочетаний без повторений и обобщенному правилу произведения имеем, что:

 

 

Интерпретации:

1) r-сочетания из n-множества

Pn(n-r,r)

2) Pn(1,1,1,1…,1) – перестановка

 

 

1. Комбинаторные задачи о покрытиях, укладках, разбиениях. Примеры. Теорема о числе разбиений элементов множества на 2,3,…,k классов, с учетом их порядка в классах и без ограничений на занятость класса. Доказательства. Следствия (класс – то же, что и ящик).

 

1. Интерпретация комбинаторных операций выборки и упорядочивания как отображения множеств. Примеры. Условие существования взаимно-однозначных отображений.
2. Интерпретация комбинаторных операций выборки и упорядочивания как отображения множеств. Примеры. Условие существования отображения N на K. Сформулировать и доказать теоремы…

Абстракция – большинства комбинаторных задач изложено с использованием этой интерпретации

Операция размещения представляет собой по существу функциональное отношение, с которым связывают функцию f, область определения, которая является множеством N, а область значений множество N.

Такое соответствие в современной математике называют отображением и обозначают <N,K,f>

 

Виды:

Map (N,K)= {f:N -> K, f - произвольная} N в K

Усл. сущ.: Map (N,K)!= 0 всегда

 

Sur (N,K)= {f:N -> K, f – сюрьективное} N на K

Усл. сущ.: Sur (N,K)!= 0 => |N|>=|K|

 

Inj (N,K)= {f:N -> K, f - инъективное}

Усл. сущ.: Inj (N,K)!= 0 => |N|=<|K|

 

Bij (N,K)= {f:N -> K, f - биективное} взаимнооднозначное отношение

Усл. сущ.: Inj (N,K)!= 0 => |N|=|K|