n元集的幂等变换的个数

hbghlyj

$n$元集的幂等变换的个数为$$i(n)=\sum_{k=1}^n\binom nkk^{n-k}$$
指数生成函数为$$\sum_{n=0}^\infty i(n)\frac{x^n}{n!}=e^{xe^x}$$
其中$i(0)=1$

hbghlyj

回复 1# hbghlyj
Idempotent functions
If the set $E$ has $n$ elements, we can partition it into $k$ chosen fixed points and $n-k$ non-fixed points under $f$, and then $k^{n-k}$ is the number of different idempotent functions. Hence, taking into account all possible partitions,
\[ \sum _{k=0}^{n}{n \choose k}k^{n-k}\]
is the total number of possible idempotent functions on the set. The integer sequence of the number of idempotent functions as given by the sum above for n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... starts with 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, ... (sequence A000248 in the OEIS).

---

例如$n=2,k=2$时, 先从1,2,3,4中选出$n-k$个元素(例如3,4)作为非不动点(non-fixed point), 有$\binom nk$种方式.
把$n-k$个非不动点(例如3,4)映射到$k$个不动点(例如1,2)有$k^{n-k}$个函数.