Сколько функций на конечном множестве

[Qlin]

Сколько существует функций на конечном множестве мощности $n$ таких, что $f(f(x))=f(x)$ ?

Я знаю, что общее число функций равно $n^n$, но как выбрать из них те самые?

[Connector]

Я бы размышлял так: множество определения любой функции, определенной в множестве $M$ заданной мощности, можно разбить на пересечение с её множеством значений и разность с этим множеством (то есть, если $f$ определена на множестве, как в условии, то это будут множество значений и его дополнение до $M$). На пересечении функция должна быть тождественной; на разности её можно определить как угодно...
(Отсюда уже видно, как получить формулу для числа функций, но она будет довольно сложной).

[ewert]

ИСН в сообщении #1401751 писал(а):

У нас множество значений - это всё M. Она не должна быть на нём тождественной

Нет. Нет

[george66]

А что, должна быть простая формула? Какую-то формулу я могу выписать (идея выше изложена - берём любое подмножество, рассматриваем функции, для которых эти точки неподвижные), но там надо суммировать по всем подмножествам. Это задача из учебника?

[ИСН]

Мне было показалось, что там написано $f(f(x))=x$. Но нет, это другая задача с другим ответом, тоже нетривиальным.

[ET]

george66 в сообщении #1401832 писал(а):

А что, должна быть простая формула?

Похоже, что не должна быть. Если записать эту формулу со значком суммы, расчитать на компе первые несколько значений, то по ним можно найти последовательноть в ОЕИС. А там ничего лучше, чем той формулы, пот котрой я считал, не видно

-- Пт июн 28, 2019 12:56:12 --

Qlin в сообщении #1401715 писал(а):

Сколько существует функций на конечном множестве мощности $n$ таких, что $f(f(x))=f(x)$ ?

Я знаю, что общее число функций равно $n^n$, но как выбрать из них те самые?

Выпишите число таких функций имеющих $n$ неподвижных точек, $n-1$ неподвижных точек, $n-2$ неподвижных точек итд. Просуммируйте. Получится что-то похожее на бином Ньютона. Лучшего там, похоже, не будет