Лемма 1. Если |X| = n, |Y | = m, то количество всех функций
f : X → Y равно mn
.
Эквивалентное утверждение. Число слов длины n в алфавите
из m символов равно mn
.
Доказательство. Без потери общности можно всегда считать,
что X = {1, ..., n}, Y = {1, ..., m}. Каждую функцию можно
тогда отождествить с последовательностью
< f (1), ..., f (n) >=< y1, ..., yn >. Каждый член yi
последовательности можно выбрать m способами, что дает mn
возможностей выбора последовательности < y1, ..., yn >.