Hai sei pacchetti regalo e tre amici a cui consegnarli. Vuoi assicurarti che nessuno di loro resti a mani vuote. Sembra un problema banale, quasi quotidiano, ma nasconde una delle sfide più interessanti della combinatoria: come distribuire un set di elementi in modo che ogni ‘contenitore’ riceva almeno un’unità.
In matematica, questo si traduce nel calcolo delle funzioni suriettive. Non si tratta solo di applicare una formula a memoria, ma di capire come ‘pulire’ il totale delle possibilità da quei casi fastidiosi in cui qualcuno rimane escluso. Se vi siete mai chiesti come gli algoritmi di allocazione delle risorse decidano come non lasciare nessuno a secco, la risposta parte da qui.
Quesito – Livello difficile
Quante sono le funzioni suriettive da un insieme [math]A[/math] di 6 elementi a un insieme [math]B[/math] di 3 elementi?
Ricordiamo che una funzione è suriettiva se ogni elemento del codominio viene utilizzato almeno una volta.
Suggerimento: utilizza il principio di inclusione-esclusione.
Risposte possibili:
- A) 540
- B) 729
- C) 720
- D) 365
Soluzione
Passo 1 – Capire il problema
Abbiamo:
- un insieme di partenza [math]A[/math] con 6 elementi;
- un insieme di arrivo [math]B = \{1,2,3\}[/math] con 3 elementi.
Vogliamo contare solo le funzioni che “usano” tutti e tre gli elementi del codominio.
Passo 2 – Contiamo prima tutte le funzioni possibili
Ogni elemento di [math]A[/math] può essere mandato indipendentemente in uno dei 3 elementi di [math]B[/math]. Quindi il numero totale di funzioni (senza alcuna restrizione) è:
[math]3^6 = 729[/math]
👉 Perché partiamo da qui? Perché è molto più facile contare tutte le funzioni e poi togliere quelle che non sono suriettive, piuttosto che contare direttamente solo quelle buone.
Passo 3 – Individuiamo le funzioni NON suriettive
Una funzione non è suriettiva se manca almeno un elemento del codominio. Definiamo quindi:
- [math]A_1[/math]: insieme delle funzioni che non usano l’elemento 1
- [math]A_2[/math]: insieme delle funzioni che non usano l’elemento 2
- [math]A_3[/math]: insieme delle funzioni che non usano l’elemento 3
Le funzioni non suriettive sono quelle che appartengono ad almeno uno di questi insiemi.
Passo 4 – Calcoliamo le cardinalità dei singoli insiemi
Funzioni che non usano un elemento (ad esempio 1): Se una funzione non usa l’elemento 1, allora ogni elemento di [math]A[/math] può andare solo in [math]\{2,3\}[/math]. Numero di tali funzioni:
[math]2^6 = 64[/math]
Lo stesso vale per [math]A_2[/math] e [math]A_3[/math]:
[math]|A_1| = |A_2| = |A_3| = 64[/math]
Passo 5 – Calcoliamo le intersezioni a due a due
Ad esempio [math]A_1 \cap A_2[/math]: funzioni che non usano né 1 né 2. In questo caso:
- l’unica immagine possibile è 3;
- quindi esiste una sola funzione, quella che manda tutti gli elementi di [math]A[/math] in 3.
[math]|A_1 \cap A_2| = 1[/math]
Analogamente:
[math]|A_1 \cap A_3| = 1, \quad |A_2 \cap A_3| = 1[/math]
Passo 6 – Intersezione tripla
[math]A_1 \cap A_2 \cap A_3[/math] sarebbe l’insieme delle funzioni che non usano nessuno degli elementi 1, 2 e 3. Questo è impossibile, quindi:
[math]|A_1 \cap A_2 \cap A_3| = 0[/math]
Passo 7 – Applichiamo il principio di inclusione-esclusione
Il numero di funzioni non suriettive è:
[math]\displaystyle \begin{aligned}
&|A_1| + |A_2| + |A_3| \\
&{} \quad – |A_1 \cap A_2| – |A_1 \cap A_3| – |A_2 \cap A_3| \\
&{} \quad + |A_1 \cap A_2 \cap A_3|
\end{aligned}[/math]
Sostituendo i valori:
[math]3 \cdot 64 – 3 \cdot 1 + 0 = 192 – 3 = 189[/math]
Passo 8 – Otteniamo le funzioni suriettive
[math]\text{Funzioni suriettive} = 729 – 189 = 540[/math]
✅ Risposta corretta: A) 540
Osservazione
Esiste una formula generale:
[math]\text{Sur}(n,m) = m! \cdot S(n,m)[/math]
dove [math]S(n,m)[/math] è il numero di Stirling di seconda specie, cioè il numero di modi di partizionare un insieme di [math]n[/math] elementi in [math]m[/math] sottoinsiemi non vuoti.
Nel nostro caso:
- [math]S(6,3) = 90[/math]
- [math]3! = 6[/math]
- [math]6 \cdot 90 = 540[/math]
Stesso risultato, metodo diverso.
Mentre il calcolo manuale è perfetto per esami e test logici, l’approccio computazionale (Stirling) è quello che scala quando gli elementi diventano migliaia:
Snippet Python per costruire la tabella dei numeri di Stirling del secondo tipo
con ricorrenza: S(n, m) = S(n-1, m-1) + m * S(n-1, m)
n\m 1 2 3
1 1 0 0
2 1 1 0
3 1 3 1
4 1 7 6
5 1 15 25
6 1 31 90
Spiegazione del codice
Il codice implementa un approccio di programmazione dinamica per generare la tabella dei valori [math]S(n,m)[/math]. Viene creata una matrice (lista di liste) per memorizzare i risultati intermedi, ottimizzando il calcolo che altrimenti richiederebbe una ricorsione molto onerosa.
Passaggi chiave dell’algoritmo:
- Inizializzazione: Viene creata una matrice di zeri di dimensione [math](max\_n+1) \times (max\_m+1)[/math]. Questo spazio extra serve per gestire agevolmente gli indici che partono da 1.
- Iterazione del Dominio: Per ogni [math]n[/math] da 1 a [math]max\_n[/math] e per ogni [math]m[/math] da 1 a [math]max\_m[/math], il codice applica la logica di costruzione:
- Se [math]m > n[/math], il valore rimane [math]0[/math] (impossibile avere più sottoinsiemi che oggetti).
- Se [math]m = 1[/math] oppure [math]m = n[/math], il valore viene impostato a [math]1[/math] (questi rappresentano i casi base della partizione).
- Altrimenti, il valore viene calcolato usando la formula di ricorrenza:[math]S(n, m) = S(n-1, m-1) + m \cdot S(n-1, m)[/math]
- Output: Alla fine, il codice stampa la tabella in formato testuale, organizzando [math]n[/math] come righe e [math]m[/math] come colonne per una lettura immediata.
Personalizzazione del calcolo:
Puoi modificare i parametri [math]max\_n[/math] e [math]max\_m[/math] nella chiamata alla funzione build_stirling_table(6, 3) per espandere la tabella. Ad esempio:
Per [math]n=5[/math] e [math]m=5[/math], otterresti l’ultima colonna con valore [math]1[/math] per [math]S(5,5)[/math], poiché esiste un solo modo di dividere 5 oggetti in 5 sottoinsiemi non vuoti (mettere ogni oggetto da solo).
Domanda di riflessione finale
Come cambierebbe il risultato se volessimo contare le funzioni iniettive?
Per rispondere, basta ricordare la condizione fondamentale dell’iniettività:
Una funzione è iniettiva solo se elementi diversi del dominio hanno immagini diverse.
Questo implica un vincolo strutturale molto semplice:
[math]|A| \le |B|[/math]
Perché se il dominio ha più elementi del codominio, due elementi saranno costretti a “collidere” sulla stessa immagine (per il Principio dei Cassetti), violando l’iniettività.
Nel nostro caso:
- [math]|A|=6[/math]
- [math]|B|=3[/math]
E poiché [math]6 > 3[/math], non esiste alcuna funzione iniettiva da [math]A[/math] a [math]B[/math].
Risultato:
[math]\text{Funzioni iniettive} = 0[/math].
Questa domanda finale non è un dettaglio tecnico: è un modo per far emergere la differenza concettuale tra suriettività e iniettività.
- La suriettività riguarda il codominio: “tutti devono essere usati”.
- L’iniettività riguarda il dominio: “nessuno deve essere duplicato”.
Nel problema delle funzioni suriettive, il vincolo è “non lasciare nessuno a mani vuote”.
Nel problema delle funzioni iniettive, il vincolo sarebbe “non dare due pacchetti allo stesso amico”.
Ma con 6 pacchetti e solo 3 amici, è matematicamente impossibile evitare duplicazioni. Ecco perché il numero di funzioni iniettive è zero.
Schema–riassunto per lo studio
Obiettivo del problema
Contare le funzioni suriettive [math]f: A \to B[/math] con:
- [math]|A| = n[/math] (dominio)
- [math]|B| = m[/math] (codominio)
Suriettiva [math]\Leftrightarrow[/math] ogni elemento di [math]B[/math] è immagine di almeno un elemento di [math]A[/math].
Strategia generale
- Contare tutte le funzioni possibili.
- Sottrarre le funzioni non suriettive.
- Usare il principio di inclusione–esclusione.
👉 È più facile togliere le funzioni “sbagliate” che contare direttamente quelle “giuste”.
Numero totale di funzioni
Ogni elemento del dominio può essere mandato in uno qualsiasi degli [math]m[/math] elementi del codominio.
[math]\text{Funzioni totali} = m^n[/math]
Nel caso [math]n=6, m=3[/math]: [math]3^6 = 729[/math]
Individuare le funzioni NON suriettive
Una funzione non è suriettiva se manca almeno un elemento del codominio. Definiamo:
[math]A_i[/math]: insieme delle funzioni che non usano l’elemento [math]i[/math] del codominio.
Le funzioni non suriettive sono: [math]A_1 \cup A_2 \cup \dots \cup A_m[/math].
Cardinalità dei singoli insiemi [math]A_i[/math]
Se una funzione non usa un certo elemento, restano solo [math]m-1[/math] possibili immagini.
[math]|A_i| = (m-1)^n[/math]
Nel caso [math]m=3, n=6[/math]: [math]2^6 = 64[/math]
Intersezioni a due a due
Se una funzione non usa due elementi del codominio, restano [math]m-2[/math] valori possibili.
[math]|A_i \cap A_j| = (m-2)^n[/math]
Nel caso [math]m=3[/math]: [math]1^6 = 1[/math]
Intersezione totale
Se una funzione non usa nessun elemento del codominio, essa non può esistere:
[math]|A_1 \cap A_2 \cap \dots \cap A_m| = 0[/math]
Principio di inclusione–esclusione
Numero di funzioni non suriettive:
[math]\sum |A_i| – \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| – \dots[/math]
Nel caso [math]n=6, m=3[/math]: [math]3 \cdot 64 – 3 \cdot 1 + 0 = 189[/math]
Formula finale
[math]\text{Funzioni suriettive} = m^n – \text{funzioni non suriettive}[/math]
Nel nostro caso: [math]729 – 189 = 540[/math]
Formula alternativa (teorica)
[math]\text{Sur}(n,m) = m! \cdot S(n,m)[/math]
Dove [math]S(n,m)[/math] rappresenta i numeri di Stirling di seconda specie, che contano le partizioni di [math]n[/math] elementi in [math]m[/math] blocchi non vuoti.
Per [math]n=6, m=3[/math]: [math]3! \cdot S(6,3) = 6 \cdot 90 = 540[/math]
Caso confronto: funzioni iniettive
Una funzione iniettiva richiede [math]|A| \le |B|[/math]. Se [math]n > m[/math]:
Nessuna funzione iniettiva (risultato 0)
L’anima del problema: Oltre i numeri
Questo esercizio non è solo un rompicapo da esame di Analisi o Algebra Lineare; è un modello di efficienza distributiva.
Ecco perché è un “classico” che ogni studente STEM dovrebbe masticare:
-
Il potere del “Complementare”: Invece di contare direttamente le configurazioni difficili, contiamo tutto e sottraiamo l’errore. È una mentalità fondamentale nel Debugging e nella Cybersecurity (contare i vettori di attacco esclusi).
-
Data Science e Clustering: Quando suddividiamo un dataset in k cluster, stiamo cercando una funzione suriettiva dal set di dati al set di etichette. Se un cluster è vuoto, il nostro modello di clustering ha fallito.
-
Load Balancing: In informatica, distribuire 6 task su 3 server assicurandosi che nessun server sia inattivo è esattamente il calcolo che abbiamo appena fatto.
Le funzioni suriettive sono le fondamenta della logica con cui evitiamo lo spreco di risorse.
Funzioni & Combinatoria
📘 Capire le funzioni – definizioni fondamentali e test
📘 Funzioni iniettive – definizione, proprietà ed esempi
📘 Funzioni suriettive – guida completa con esempi
📘 Test di Analisi 1: 14 esercizi su insiemi, funzioni e successioni
📘 Calcolo combinatorio: esercizi risolti passo-passo (disposizioni, inclusione-esclusione)
📘 Calcolo combinatorio al tema d’esame – esercizi su permutazioni, combinazioni e disposizioni
(70)
Altri articoli nella categoria "Calcolo combinatorio"
- Come Risolvere le Equazioni con i Fattoriali: Esercizi Svolti, Formule e Strategie
- Test di Calcolo Combinatorio: Esercizi Svolti sulle Permutazioni (Base e Avanzati)
- Combinazioni con Ripetizione: Test, Esercizi Svolti e Formule Spiegate
- Calcolo Combinatorio Pratico: 6 Esercizi Svolti dal Principio di Moltiplicazione ai Vincoli Complessi
- Combinatoria Applicata: 8 Esercizi Risolti per Distinguere Disposizioni, Combinazioni e Permutazioni con Vincoli
- Guida pratica alle Disposizioni nel Calcolo Combinatorio: Formule ed Esercizi Progressivi
- Disposizioni con Ripetizione: Guida Completa con Esercizi Svolti (Livello Base, Intermedio, Avanzato)
- Permutazioni Circolari: Guida Pratica con 6 Esercizi Risolti
- Lemma di Burnside: La Guida Completa al Conteggio delle Configurazioni Distinte con Simmetrie
- Combinatoria Avanzata: Soluzioni Dettagliate a Problemi di Conteggio con Simmetrie e Vincoli