Доказательство. Рис. 2.2. Решение уравнения x1 + ××× +xn = k

Каждому решению x₁ + ××× +x_n = k соответствует неубывающая последовательность y₁ ≤y₂ ≤ _{× × ×} ≤y_n-1, где y₁=x₁, y₂ = y₁+x₂, ×××, y_n-1 = y_n-2 + x_n-1.

Теорема 7. .

Доказательство. Рассмотрим график неубывающей функции

Рис. 2.3. График неубывающей функции

График задается последовательностью из 0 и 1

0 0 1 1 0 0 … 0 1 0 0 … 1 1 … 1

состоящей из n-1+k разрядов, имеющих k единиц.

Следствие 1. равно числу неубывающих функций

{1,2, ×××, k } ® {1,2, ×××, n }.

Доказательство. Первый способ: транспонировать графики. Если график, показанный на рис.2.3, отразить относительно прямой y = x, то получим график функции {1,2, ×××, k } ® {1,2, ×××, n }. Это доказывает утверждение следствия.

Второй способ: число неубывающих функций {1,2, ×××, k } ® {1,2, ×××, n } равно = = .

Получаем следующую таблицу 2.2, содержащую числа конфигураций

Таблица 2.2

Число конфигураций

	функций m®n	неубывающих функций m®n
Всех	nm
Инъективных
Сюръективных	?
Биективных	n!, если m=n, иначе 0	1, если m=n, иначе 0

Здесь m = {0,1, ×××, m-1}. Например, число неубывающих сюръективных отображений {0,1, ×××, m -1} ® {0,1, ×××, n -1} равно .

Поиск по сайту: