Baltic Way 2019

Lemma. Let $A$ be a set of $a$ consecutive integers and let $B$ be a set of $b$ consecutive integers. There are exactly $\left(\genfrac{}{}{0ex}{}{a+b-1}{a}\right)$ nonincreasing functions $f:A\to B$. Proof. Let (wlog) $A=\{1,\dots ,a\}$, $B=\{1,\dots ,b\}$. A function $f:A\to B$ is nonincreasing if and only if the function $g:A\to C=\{1,\dots ,a+b-1\}$ given by $g(x)=f(x)+(a-x)$ is strictly decreasing. Any such function $g$ is uniquely identified with the set of its values $g(A)$; and the latter has size $a$. So there are as many functions $f$ in question as there are $a$-element subsets of $C$; the lemma is ready.

Now we count the functions of the two types under consideration. A function $f$ that has a fixed-point $c\in \{1,\dots ,n\}$ maps $\{1,\dots ,c-1\}$ (nonincreasingly) into $\{c,\dots ,n\}$, and it maps $\{c+1,\dots ,n\}$ (nonincreasingly) into $\{1,\dots ,c\}$; and there are no further restrictions. So, on the left side of $c$, we have (by the lemma with $a=c-1,b=n-c+1$) $\left(\genfrac{}{}{0ex}{}{n-1}{c-1}\right)$ choices; and right to $c$ (again by the lemma, with $a=n-c,b=c$) we have also $\left(\genfrac{}{}{0ex}{}{n-1}{c-1}\right)$ choices. The number of nonincreasing functions with a fixed-point is therefore equal to $$F_n=\sum _{c=1}^n\left(\genfrac{}{}{0ex}{}{n-1}{c-1}\right)\left(\genfrac{}{}{0ex}{}{n-1}{c-1}\right).$$ If $f$ has no fixed-point then there exists $c\in \{1,\dots ,n-1\}$ such that $f(x)>x$ for $x\le c$ and $f(x)<x$ for $x>c$. A similar reasoning applies: $f$ maps $\{1,\dots ,c\}$ into $\{c+1,\dots ,n\}$ and it maps $\{c+1,\dots ,n\}$ into $\{1,\dots ,c\}$ (arbitrarily nonincreasingly). On the left piece (lemma with $a=c,b=n-c$) there are $\left(\genfrac{}{}{0ex}{}{n-1}{c}\right)$ choices; on the right piece (lemma, $a=n-c,b=c$) $\left(\genfrac{}{}{0ex}{}{n-1}{c-1}\right)$ choices. So the number of nonincreasing functions without a fixed-point equals $$G_n=\sum _{c=1}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{c}\right)\left(\genfrac{}{}{0ex}{}{n-1}{c-1}\right).$$ Consider the polynomial $P_n(x)=(1+x{)}^{n-1}$. We recognize $F_n$ and $G_n$ as the coefficients of $x^{n-1}$ and $x^n$ in the product $P_n(x)P_n(x)=(1+x{)}^{2n-2}$. Thus $F_n=\left(\genfrac{}{}{0ex}{}{2n-2}{n-1}\right)$ and $G_n=\left(\genfrac{}{}{0ex}{}{2n-2}{n}\right)$, with the difference $F_n-G_n=\left(\genfrac{}{}{0ex}{}{2n-2}{n-1}\right)-\left(\genfrac{}{}{0ex}{}{2n-2}{n}\right)$. (This gets us another characterization of Catalan numbers.)