Упражнение. Сколько существует различных функций из в если

Сколько существует различных функций из в если

Ответ:

Сочетания с повторениями

Неупорядоченная выборка, в которой элементы могут повторяться, называется сочетанием с повторениями. Число всех сочетаний с повторениями из n по r будем обозначать

ТЕОРЕМА. (1)

Доказательство аналогично выводу формулы Паскаля.

ТЕОРЕМА. (2)

Доказательство. Проведем индукцию по n. База индукции есть: Пусть формула верна для Положим Докажем с помощью индукции по r равенство При r = 1 имеем т.е. база индукции есть. Пусть формула верна при r = s, т.е. _. Тогда при r = s + 1 по формуле (1) и гипотезе индукции