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?

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.
