[A/L] (2021/22) Induzione - Esercizio 15

[matypist]

[Exyss]

Credo sia abbastanza autoesplicativo, poiché una funzione biettiva F : X -> Y dove #X = #Y equivale ad effettuare delle distribuzioni semplici di N elementi

[GattoBrizzolato]

.

[LuginiAndrea]

Spiego solo il passo induttivo in quanto il caso base è banale.
Abbiamo sia $X$ che $Y$ con $n+1$ elementi:
prendiamo l'$n+1$-esimo elemento tdi $Y$, chiamiamolo $y$ rimuoviamolo da $Y$.
Scegliamo ora un elemento $x \in X$ scelto in modo tale che $x \rightarrow y$.
Abbiamo $n+1$ modi di scegliere questo elemento.
Ci rimangono ora $X - x, Y - y$ con $n$ elementi, e sappiamo che le biezioni fra i due sono $n!$.
La risposta risulta quindi $\left(n+1\right) \times n! = \left(n+1\right)!$, ovvero i modi di scegliere $x \rightarrow y$ ed i modi di mettere in biezione i restanti elementi