Proposizione 4 Sia un intero positivo.
L’insieme
ha
elementi.
L'idea della dimostrazione è la seguente:
Si costruiscono tutte le permutazioni di ponendo i valori
numerici nella seconda riga della tabella
in tutti i modi possibili.
Si consideri ; esso può assumere i valori
, cioè ci sono
modi per rimpiazzare
con un valore
numerico.
Una volta fissato , ci sono
possibilità per
: tutti gli interi
, all’infuori di
(è una biiezione!).
Fissato anche , per
si hanno
possibilità, e così
via.
Il numero delle permutazioni di è allora
□
Esempio 5 Seguendo la dimostrazione della
proposizione 4 , costruiamo le permutazioni di
. Se
,
.
Per si hanno tre
possibilità:
,
,
.
Nel primo caso, , si ha:
e quindi
,
oppure
e quindi
,
cioè si ottengono le permutazioni
,
.
Nel secondo caso, , si ha:
e quindi
,
oppure
e quindi
,
cioè si ottengono le permutazioni
,
.
Infine se , si ha:
e quindi
,
oppure
e quindi
,
cioè si ottengono le permutazioni
,
.
Abbiamo in questo modo ottenuto
tutti i sei elementi di .