QII.B.2
Combinations & Selection
Counting Functions or Mappings with Constraints
View
For every pair $(p, k)$ of nonzero natural numbers, we denote by $S(p, k)$ the number of surjections from $\llbracket 1, p \rrbracket$ to $\llbracket 1, k \rrbracket$. Consistently, for every $p \in \mathbb{N}^*$, we set $S(p, 0) = 0$.
For $p \geqslant n$, establish the formula $$n^p = \sum_{k=0}^{n} \binom{n}{k} S(p, k)$$ where $S(p, 0) = 0$ by convention.