Задача 61528

Темы:    [ Раскладки и разбиения ] [ Сочетания и размещения ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 4 Классы: 8,9,10,11

Условие

Докажите, что  
Числа P_kl(n) определены в задаче 61525.

Решение

Сумма в условии равна количеству наборов вида  {a₁, a₂, ..., a_k},  где  0 ≤ a₁ ≤ a₂ ≤ ... ≤ a_k ≤ l.  Поставим в соответствие такому набору подмножество
{a₁ + 1, a₂ + 2, ..., a_k + k}  множества  {1, 2, ..., l + k}.  Нетрудно проверить, что так получаются все подмножества из k элементов указанного множества, причём по одному разу. Следовательно, наших наборов ровно  

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	11
Название	Последовательности и ряды
Тема	Последовательности
параграф
Номер	4
Название	Многочлены Гаусса
Тема	Последовательности
задача
Номер	11.101