# Combinatorial proof for Touchard's congruence

Bell number denoted $$B_n$$ is the number of ways to partition a set with cardinality $$n$$ into $$k$$ indistinguishable sets , where $$0\le k\le n$$

It's known that Bell numbers obey Touchard's Congruence which is as follows:

Assuming $$p$$ is a prime number, then: $$B_{\,p^m+n}≡mB_n+B_{n+1}\,\,\,\mod p$$

Which is a generalization of the relation: $$B_{\,p+n}≡B_n+B_{n+1}\,\,\,\,\,\,\mod p$$

The following theorem is a statement which is necessary to prove Touchard's Congruence:

For positive integer $$n$$ and $$j$$:

$$B_{n+j}=\sum_{k=0}^{n}P_{j}\left(k\right){n\brace k}$$

Where:

$$P_{j}\left(x\right)=\sum_{r=0}^{j}B_{j-r}{{j}\choose{r}}x^{r}$$

This theorem has been proven using induction, but the first one who came up with this relation did not use induction and surely there is another idea behind this theorem, I'm asking if this theorem has any combinatorial proof.

Fix $$n$$ of the $$n+j$$ elements. Build a partition of the $$n+j$$ elements starting from a partition of the $$n$$ elements into $$k$$ sets, of which there are $$\left\{n\atop k\right\}$$. Pick $$r$$ of the remaining $$j$$ elements in one of $$\binom jr$$ ways. These $$r$$ elements are added to the existing sets in one of $$k^r$$ ways, whereas the remaining $$j-r$$ elements form additional sets in one of $$B_{j-r}$$ ways. Now sum over $$k$$ and $$r$$.

We seek to show that

$$B_{n+j} = \sum_{k=0}^n {n\brace k} \sum_{r=0}^j B_{j-r} {j\choose r} k^r.$$

This is $$\sum_{k=0}^n {n\brace k} j! [z^j] \left(\sum_{q\ge 0} k^q \frac{z^q}{q!}\right) \exp(\exp(z)-1) \\ = j! [z^j] \exp(\exp(z)-1) \sum_{k=0}^n {n\brace k} \exp(kz) .$$

Now we have

$${n\brace k} = n! [w^n] [u^k] \exp(u(\exp(w)-1))$$

so that

$$\sum_{k=0}^n {n\brace k} u^k = n! [w^n] \exp(u(\exp(w)-1))$$

and we get for the sum

$$j! [z^j] \exp(\exp(z)-1) n! [w^n] \exp(\exp(z)(\exp(w)-1)) \\ = j! [z^j] n! [w^n] \exp(\exp(z)\exp(w)-1) \\ = j! [z^j] n! [w^n] \exp(\exp(z+w)-1) \\ = j! [z^j] n! [w^n] \sum_{q\ge 0} B_q \frac{(z+w)^q}{q!} \\ = j! n! [w^n] \sum_{q\ge j} B_q \frac{1}{q!} {q\choose j} w^{q-j} \\ = j! n! B_{n+j} \frac{1}{(n+j)!} {n+j\choose j} = B_{j+n}.$$

This is the claim.

Remark. On the second line we have used the fact that when we multiply two exponential generating functions of the sequences $$\{a_n\}$$ and $$\{b_n\}$$ we get that

$$A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$