I foglietti sono funzioni

C’è un modo profondo — e sorprendentemente semplice — di vedere le quattro formule dei foglietti: contano funzioni.

Numeriamo i foglietti $1,2,\dots,k$ e le persone $1,2,\dots,n$. Distribuire i foglietti significa dire, per ciascun foglietto, a quale persona va: cioè assegnare a ogni elemento dell’insieme $K=\{1,\dots,k\}$ (i foglietti, il dominio) un elemento dell’insieme $N=\{1,\dots,n\}$ (le persone, il codominio). Questa è esattamente una funzione $f:K\to N$, dove $f(i)$ è la persona che riceve il foglietto $i$.

Le due domande dei foglietti diventano allora due proprietà della funzione:

• numerati / bianchi = i foglietti sono distinguibili o no. Se sono numerati, conta quale foglietto va a chi: la funzione è quella che è. Se sono bianchi, i foglietti sono intercambiabili, quindi conta solo quanti e a chi, non l’etichetta: di tutte le funzioni che danno lo stesso “risultato” ne teniamo una sola, quella che manda i foglietti in ordine — cioè una funzione crescente (o non decrescente, se si può ripetere).
• max 1 / più di uno a testa = ogni persona riceve al più un foglietto, oppure quanti se ne vuole. “Al più uno a testa” significa che due foglietti diversi non finiscono sulla stessa persona: la funzione è iniettiva.

Mettendo insieme le due proprietà si ottengono i quattro tipi di funzione — ed ecco le quattro formule:

Le quattro formule contano funzioni $f:K\to N$ (con $|K|=k$, $|N|=n$)

	fogli bianchi (uguali)	fogli numerati (distinti)
max 1 a persona	funzioni strettamente crescenti — $\dbinom{n}{k}$	funzioni iniettive — $\dfrac{n!}{(n-k)!}$
anche più di uno	funzioni non decrescenti — $\dbinom{n+k-1}{k}$	tutte le funzioni — $n^k$

Vediamo i quattro casi uno per uno, con un esempio da $k=3$ foglietti a $n=5$ persone.

Numerati, più di uno a testa → tutte le funzioni ($n^k$)

Nessun vincolo: ogni foglietto sceglie liberamente una delle $n$ persone. Il foglietto $1$ ha $n$ scelte, il $2$ ne ha $n$, …, il $k$ ne ha $n$: in tutto $n\cdot n\cdots n = n^k$. Sono tutte le funzioni da $K$ a $N$. Le frecce possono incrociarsi, arrivare sulla stessa persona, lasciarne fuori altre.

Qui $f(1)=2,\ f(2)=2,\ f(3)=5$: due foglietti sulla stessa persona, tre persone senza nulla. Va benissimo.

Numerati, max 1 a testa → funzioni iniettive ($n!/(n-k)!$)

Ogni persona al più un foglietto: due foglietti diversi non possono finire sulla stessa persona. Il foglietto $1$ ha $n$ scelte, il $2$ solo $n-1$ (deve evitare la persona già occupata), il $3$ ha $n-2$, …: $n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}$. Sono le funzioni iniettive: nessuna persona riceve due frecce.

Qui $f(1)=4,\ f(2)=1,\ f(3)=3$: immagini tutte diverse, ma l’ordine può “incrociarsi” (il foglietto $1$ va più in basso del $2$). L’ordine è libero perché i foglietti sono numerati.

Bianchi, max 1 a testa → funzioni strettamente crescenti ($\binom{n}{k}$)

Ora i foglietti sono uguali: non possiamo più distinguere “il foglietto $1$” dal "$2$". Con al più uno a testa, distribuire significa solo scegliere quali $k$ persone ricevono un foglietto — un sottoinsieme di $k$ persone su $n$. Per contarli senza doppioni, li elenchiamo sempre in ordine crescente: ogni scelta corrisponde a un’unica funzione strettamente crescente $f(1)<f(2)<\dots<f(k)$. Le frecce non si incrociano e sono tutte distinte. Numero: $\dbinom{n}{k}$.

Qui $f(1)=1<f(2)=3<f(3)=4$: immagini crescenti, frecce che non si incrociano. Equivale a scegliere il sottoinsieme $\{1,3,4\}$ delle persone.

Bianchi, più di uno a testa → funzioni non decrescenti ($\binom{n+k-1}{k}$)

Foglietti uguali, ma ora si può darne più di uno alla stessa persona. Conta solo quante volte ciascuna persona è scelta: elencando di nuovo le immagini in ordine otteniamo una funzione non decrescente $f(1)\le f(2)\le\dots\le f(k)$ (le uguaglianze corrispondono ai foglietti dati alla stessa persona). Le frecce non si incrociano, ma possono arrivare insieme. Numero: $\dbinom{n+k-1}{k}$.

Qui $f(1)=1\le f(2)=1\le f(3)=4$: la persona $1$ riceve due foglietti, la $4$ uno. Non decrescente, frecce non incrociate.

Riassunto in una riga

Passando da numerati a bianchi si passa da funzioni qualunque/iniettive alle loro versioni ordinate (non decrescenti/strettamente crescenti): i foglietti uguali “cancellano l’ordine”, e ordinare le immagini è il modo di contarle una volta sola.

Collegamenti

Argomenti: Combinatoria
Concetti: Coefficiente binomiale · Combinazioni · Disposizioni · Dominio codominio · Iniettivita · Permutazioni
Metodi: Tabella foglietti
Competenze: Calcolo combinatorio · Modellizzare