флеров

Количество сюръективных отображений

Вернемся теперь к задаче вычисления количества сюръективных отображений конечного множества X из n элементов на конечное множество Y из m элементов.

Теорема 1.14. Число сюръективных отображений конечного множества X , |X| = n, на конечное множество Y, |Y| = m, то есть число функций, таких, что f(X)=Y, равно

Доказательство.

Пусть Y={y₁ ,...,y_m}. Обозначим через _i следующее свойство функции : функция , такова, что . Пусть - множество функций, обладающих свойством _i . Тогда очевидно, что

Число всех функций равно mⁿ .

Для произвольной последовательности , такой что , . Именно столько имеется функций . i-элементное подмножество можно выбрать способами, и, следовательно, по формуле включений-исключений имеем

Следствие. На основании утверждения 1 .12 и доказанной теоремы имеем

Таким образом, получено еще одно явное выражение для числа разбиений. Отметим, что разумно и иногда необходимо использовать это выражение в аналитических исследованиях свойств разбиений, хотя его эффективность в вычислениях самих чисел разбиений существенно ниже непосредственного использования рекуррентного соотношения ( 1 .12).

Содержание