Counting the number of good functions Hy, happy new year everyone.
I have been stuck on the following problem for a while now, so I am posting it here in other to discuss it.
A function $g: [[1,n]] \to [[0,n]]$ is called good if :
$$\forall j \in[[1,n]] , \exists i~ \text{integer} \geq 0 , g^{i} (j)=0 $$
where $g^{i}=g\circ \dots \circ g ~~(i ~~\text{times})$
How many  such good functions  there is?
 A: First $g(x)\ne x$ for all $x$, and $g^i(x)=0 \Rightarrow i\leq n$ and there exist a number x such that $g(x)=0$. Let $k_j$ denote number of numbers $x$ s.t. $g^j(x)=0$. So to construct such function, we first select $k_1$ numbers $x$ and force $g(x)=0$ in $\binom{n}{k_1}$ modes. Then we choose $k_2$ numbers and force $g(x)\in g^{-1}(0)$ in $\binom{n-k_1}{k_2}\times k_1^{k_2}$ modes and so on... . Finally the number of functions is:
$$\sum_{k_1\geq 1, k_j\geq0 , j=2,3,\cdots n}\binom{n}{k_1}\times \binom{n-k_1}{k_2}\times k_1^{k_2}\times \binom{n-k_1-k_2}{k_3}\times k_2^{k_3}\cdots \binom{n-k_1-k_2-\cdots k_{n-1}}{k_n}\times k_{n-1}^{k_n}=\sum_{k_1\geq 1, k_j\geq0 , j=2,3,\cdots n}\binom{n}{k_1,k_2,\cdots ,k_{n}}\times  k_1^{k_2}\times k_2^{k_3}\cdots \times k_{n-1}^{k_n}$$
A: Let $A_n,B_m$ be two disjoint sets of size $n,m\in \mathbb{N}$.
Take $a(m,n)$ as the number of functions $f:A_n\rightarrow A_n \cup B_m$ satisfying the following condition: $$\forall a\in A_n \text{  } \exists i\geq 0 \text{ such that } f^i(a)\in B_m$$ You're looking to compute $a(1,n)$. Evidently $a(m,1)=m$ and $$a(m,n)=m^n+\sum_{k=1}^{n-1}m^k {n \choose k}a(k,n-k)$$ It's easily shown that $$a(n,m)=m(m+n)^{n-1}$$ solves this relation. Taking $m=1$ gives $a(1,n)=(n+1)^{n-1}$ as required.
