Un insieme finito di $n$ elementi può essere posto in corrispondenza biunivoca con l'insieme $\{1,\dots,n\}$, dunque possiamo supporre che $S=\{1,\dots,n\}$. Data una combinazione di $r$ elementi di $S$, la ordiniamo in modo che i suoi elementi si presentino in modo non decrescente. Sia essa $(i_1,\dots, i_r)$ con $1\leq i_1\leq i_2\leq\ldots\leq i_r\leq n$: le associamo la $(r{\bf +}1)$-upla $(i_1{\bf -}1,$ $i_2{\bf -}i_1,$ $i_3{\bf -}i_2,\dots ,$ $i_r{\bf -}i_{r{\bf -}1},$ $n{\bf -}i_r)$. Questa applicazione $f$ è biunivoca nell'insieme delle disposizioni di $r{\bf +}1$ numeri non negativi (cioè $\tilde S^{r{\bf +}1}$ con $\tilde S{\bf =}\{0,\dots, n{\bf -}1\}$), la cui somma è $n{\bf -}1$:
$(i_1,\dots, i_r)\mapsto$ $(i_1{\bf -}1,$ $\ i_2{\bf -}i_1,\dots ,$ $i_r{\bf -}i_{r{\bf -}1},$ $n{\bf -}i_r)$
- $f$ è iniettiva (cioè $f(x){\bf =}f(y)\ \Rightarrow \ x{\bf =}y$) infatti
$$
\left(\matrix{
i_1{\bf -}1 \cr
i_2{\bf -}i_1 \cr
\vdots \cr
i_r{\bf -}i_{r{\bf -}1} \cr
n{\bf -}i_r \cr}\right)
{\bf =}
\left(\matrix{
j_1{\bf -}1 \cr
j_2{\bf -}j_1 \cr
\vdots \cr
j_r{\bf -}j_{r{\bf -}1} \cr
n{\bf -}j_r \cr}\right)
$$
$$
\Updownarrow
$$
$$
\left\{\matrix{
i_1{\bf =}j_1 \cr
i_2{\bf =}j_2 \cr
\vdots \cr
i_{r{\bf -}1}{\bf =}j_{r{\bf -}1} \cr
i_r{\bf =}j_r \cr}\right.\ \hbox{;}
$$
- $f$ è suriettiva (cioè $\forall$ $y\in \tilde S^{r{\bf +}1}$ $\exists\ $ $x\in S^r$ tale che $f(x){\bf =}y$) infatti $\forall$ $(j_1,\dots, j_{r{\bf +}1})$ $\in$ $\tilde S^{r{\bf +}1}$ tale che $j_1{\bf +}\ldots {\bf +}j_{r{\bf +}1}{\bf =}n{\bf -}1$
$$
\left(\matrix{
i_1{\bf -}1 \cr
i_2{\bf -}i_1 \cr
\vdots \cr
i_r{\bf -}i_{r{\bf -}1} \cr
n{\bf -}i_r \cr}\right)
{\bf =}
\left(\matrix{
j_1 \cr
j_2 \cr
\vdots \cr
j_r \cr
j_{r{\bf +}1} \cr}\right)
$$
$$
\Updownarrow
$$
$$
\left\{\matrix{
i_1{\bf =}j_1{\bf +}1 \cr
i_2{\bf =}i_1{\bf +}j_2 \cr
\vdots \cr
i_{r{\bf -}1}{\bf =}i_r{\bf -}j_r \cr
i_r{\bf =}n{\bf -}j_{r{\bf +}1} \cr}\right.\ \hbox{;}
$$
- $f$ è una applicazione (cioè $\forall$ $x\in S^r$ $\exists_1$ $y\in\tilde S^{r{\bf +}1}$ tale che $f(x){\bf =}y$) (provare per esercizio).
Pensiamo poi ognuna delle $(r{\bf +}1)$-uple di cui sopra come permutazione (con ripetizione) di $n{\bf -}1$ palline (uguali fra loro) e $r$ separatori (uguali fra loro), nel modo seguente:
$$
\left.\matrix{
\underbrace{\circ..\circ} &|& \underbrace{\circ..\circ} &|\dots |& \underbrace{\circ..\circ} \cr
i_1{\bf -}1 &1& i_2{\bf -}i_1 &2\dots r& n{\bf -}i_r \cr}\right.
$$
Anche questa identificazione è biunivoca e il numero di permutazioni di due tipi di oggetti (pallina e separatore) in $n{\bf +}r{\bf -}1$ posti, in modo che i primi siano ripetuti $n{\bf -}1$ volte e i secondi $r$ volte, è, come già visto,
$$
{n{\bf +}r{\bf -}1\choose n{\bf -}1\ ,\ r}={n{\bf +}r{\bf -}1\choose r}\quad\spadesuit
$$