Counting nilpotent self-maps of $\{1,\dots,n\}$ with image of a given cardinal

მამუკა ჯიბლაძე is right, these are the Narayana numbers.

You are studying functions $f$ obeying $f(2) \leq \cdots \leq f(n)$ and $1 \leq f(j) \leq j-1$ for $2 \leq j \leq n$. Draw the path from $(1,1)$ to $(n,n)$ made up of horizontal line segments from $(j,f(j+1))$ to $(j+1,f(j+1))$ for $1 \leq j \leq n-1$ and vertical line segments from $(j,f(j))$ to $(j,f(j+1))$ for $2 \leq j \leq n$, where we formally put $f(n+1)=n$. This is a bijection between your functions and paths from $(1,1)$ to $(n,n)$ which travel up and right while staying below the line $y=x+1$. The number of such paths is the Catalan number, and you can see these paths (rotated and reflected) here for $n=5$.

You want to count $f$ according to the size of this image, which is the number of horizontal segments in the path. This is also the number of bottom left corners of the path. As Wikipedia says, Narayana numbers count paths by the number of such corners (which they call peaks, because their paths are rotated and reflected).


The answer is ${n-2\choose r-1}{n-1\choose r-1}-{n-2\choose r-2}{n-1\choose r}=\frac1{n-r}{n-2\choose r-1}{n-1\choose r}$.

Let $\{1=a_0<a_1<a_2<\ldots<a_{r-1}\}$ be the image of $\alpha\in X_{n,r}$ and denote $p_i:=\max \alpha^{-1}(a_{i-1})$ for $i=1,\ldots,r-1$. Then $p_1<p_2<\ldots p_{r-1}<n$ and $p_i\geqslant a_i$ for all $i$. Now define two lattice paths (with vertical steps $+(0,1)$ and horizontal steps $+(1,0)$). The first path goes from $A=(1,0)$ to $C=(n-r,r-1)$ and has vertices at points $(a_i-i,i-1)$ and $(a_i-i,i)$ for $i=1,\ldots, r-1$. The second goes from $B=(1,-1)$ to $D=(n+1-r,r-2)$ and has the vertices $(p_i-i+1,i-2)$ and $(p_i-i+1,i-1)$. They should be disjoint, and any disjoint pair of paths from $A$ to $C$ and from $B$ to $D$ corresponds to some nilpotent map $\alpha\in X_{n,r}$.

Note that there is no pair of disjoint paths from $A$ to $D$ and from $B$ to $C$. So we get the above formula using Lindstrőm–Gessel–Viennot lemma : the $2\times 2$ matrix which counts the lattice paths from $\{A,B\}$ to $\{C,D\}$ is just $$\pmatrix{{n-2\choose r-1}&{n-2\choose r-2}\\ {n-1\choose r}& {n-1\choose r-1} &}.$$