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?

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}$$
