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$.