Задача
COM-B2-M02-P013 Общая формула сюръекций
#13
★★★★☆ Уровень 4 из 5
Докажите, что число сюръекций из \(n\)-элементного множества в \(m\)-элементное равно \(\sum_{i=0}^{m}(-1)^i\binom mi(m-i)^n\).
Запрет: выбранное значение не используется.
Всего функций \(m^n\). Если выбраны \(i\) значений, которые не используются, то все \(n\) элементов области должны перейти в оставшиеся \(m-i\) значений: \((m-i)^n\) функций. Выбрать такие \(i\) значений можно \(\binom mi\) способами. Чередуя знаки по включениям-исключениям, получаем формулу.
Показывает, что сюръекция — это отсутствие пустых значений.