Baltic Way 2023 Shortlist

Let $\mathrm{Epi}(n,i)$ be the number of surjective functions from a set with $n$ elements to a set with $i$ elements. It is not hard to see that $S(n,i)=\frac{\mathrm{Epi}(n,i)}{i!}$. Indeed, a surjective function from $\{1,\dots ,n\}$ to $\{1,\dots ,i\}$ is the same thing as a partition of $\{1,\dots ,n\}$ into $i$ parts, together with a numbering of the blocks of the partition, from $1$ to $i$. For every partition there exists $i!$ numberings, and therefore $S(n,i)\cdot i!=\mathrm{Epi}(n,i)$.

When $1\le i\le p-1$, $\gcd (p,i!)=1$. It follows that for $1\le i\le p-1$, $S(n,i)\equiv S(m,i)(\mathrm{mod}p)$ if and only if $\mathrm{Epi}(n,i)\equiv \mathrm{Epi}(m,i)(\mathrm{mod}p)$. So it is enough to prove that if $p-1\mid m-n$ then $\mathrm{Epi}(n,i)\equiv \mathrm{Epi}(m,i)(\mathrm{mod}p)$ for all $1\le i\le p-1$.

There is a formula for $\mathrm{Epi}(n,i)$: $$\mathrm{Epi}(n,i)=\sum _{j=0}^{i-1}(-1{)}^j(i-j{)}^n\left(\genfrac{}{}{0ex}{}{i}{j}\right).$$ This formula is based on nothing more than the inclusion-exclusion principle. The number of surjective functions is the number of all functions $-i$ times the number of functions that miss one particular element $+\left(\genfrac{}{}{0ex}{}{i}{2}\right)$ times the number of functions that miss two particular elements, etc. The number of functions that miss $j$ specified elements is $(i-j{)}^n$.

Now suppose $m$, $n$ are positive integers satisfying $p-1\mid m-n$. Then $a^m\equiv a^n(\mathrm{mod}p)$ for all integers $a$. When $a$ is not divisible by $p$ this follows from Fermat's little theorem. When $a$ is divisible by $p$, both sides are zero mod $p$. But we only need the cases when $a=1,\dots ,p-1$ anyway.

It follows that if $p-1\mid m-n$ then $\mathrm{Epi}(n,i)\equiv \mathrm{Epi}(m,i)(\mathrm{mod}p)$ for all $1\le i\le p-1$, and we are done.

Lemma: For every $i>1$ and $n>i$: $$S(n,i)=i\cdot S(n-1,i)+S(n-1,i-1)$$ Proof. Select an element $x$. There are $S(n-1,i)$ ways to partition the remaining elements into $i$ different sets. By adding $x$ to any of them, we get a partition of the original set. All the partitions obtained this way are different and the only partitions that cannot be obtained this way are the ones where $x$ ends up alone. But in that case the $n-1$ other elements must form $i-1$ sets, yielding another $S(n-1,i-1)$ partitions. $\square$

Lemma: For every $p$ prime, $p>i\ge 1$ and $\lambda \ge 0$: $$S(i+\lambda (p-1),i)=1(\mathrm{mod}p).$$ Proof. As $S(n,1)=1$ and $S(i,i)=1$, this is obvious for $i=1$ or $\lambda =0$. We proceed by induction over $i$ and $\lambda$. Using the induction hypothesis and the previous lemma: $$\begin{array}{rl}S(i+\lambda (p-1),i)& =i\cdot S(i-1+\lambda (p-1),i)+S(i-1+\lambda (p-1),i-1)\\ & =i\cdot S(i-1+\lambda (p-1),i)+1\text{mod }p\end{array}$$ Otherwise applying this $p-1$ times gives $$\begin{array}{rl}S(i+\lambda (p-1),i)& =i^{p-1}\cdot S(i+(\lambda -1)(p-1),i)+\sum _{j=0}^{p-2}{i}^j\text{mod }p\\ & =i^{p-1}\cdot 1+\frac{i^{p-1}-1}{i-1}\text{mod }p\\ & =1\cdot 1+0\text{mod }p.\end{array}$$ Where the last equality holds by Fermat's little theorem as $p>i>1$ implies $i\ne 0,1(\mathrm{mod}p)$. $\square$

We can now proceed to proving the problem statement by induction: If $i=1$ the statement is obvious. If $m=i$ or $n=i$, we have the statement of the second lemma. So assume $i>1$ and $n>i$, $m>i$ and that the problem statement holds for all smaller values. Then $$\begin{array}{rl}S(n,i)-S(m,i)& =i\cdot (S(n-1,i)-S(m-1,i))+\\ & +S(n-1,i-1)-S(m-1,i-1)\\ & =i\cdot 0+0\text{mod }p\\ & =0\text{mod }p.\end{array}$$