Ricevo da Anna la seguente domanda:
"Calcola in quanti modi si possono sistemare n oggetti distinti in k scatole diverse sapendo che in ogni scatola deve esserci almeno 1 oggetto".
Es.: Calcola in quanti modi si possono sistemare 8 oggetti distinti in sei scatole diverse sapendo che in ogni scatola deve esserci almeno un oggetto.
Come lo risolverebbe in generale ?
Abbiamo trovato varie soluzioni per semplici casi, ma non una formula generale.
Grazie
Le rispondo così:
Cara Anna,
non è facile dare una “formula” semplice che esprima la soluzione generale del problema, ma proviamo ad analizzarlo. Supponi che gli n oggetti distinti siano n posti numerati in una sequenza, e che in tali posti debbano collocarsi, uno per ogni posto, n elementi presi da un insieme che ne contiene k distinti, con k minore o uguale a n, quindi con la necessità eventualmente di ripetere uno o più elementi (ad esempio i nomi A,B,C… delle scatole). Si tratta quindi di contare tutte le possibili permutazioni con ripetizione di n elementi di cui ordinatamente n1, n2, …, nk si ripetono, al variare di tutti i possibili insiemi ordinati (n1, n2, …, nk) di k numeri naturali non nulli tali che n1 + n2 + … + nk = n : in pratica si tratta di contare tutti i possibili anagrammi di parole di n lettere di cui solo k distinte, utilizzando tutte k le lettere ogni volta ma al variare di tutti i possibili casi in cui a ripetersi una o più volte sia ciascuna delle k lettere. Poiché
(n!)/( n1! n2!… nk!)
rappresenta il numero delle possibili permutazioni con ripetizione di n elementi di cui ordinatamente n1, n2, …, nk si ripetono, detto A = {(n1, n2, …, nk)/ n1 + n2 + … + nk = n et n1,n2,..,nk >=1} l’insieme di tutti le possibili k-ple ordinate (n1, n2, …, nk) di numeri naturali non nulli tali che n1 + n2 + … + nk = n, il numero cercato è esprimibile come
Somma su A [(n!)/( n1! n2!... nk!)]
Applichiamo all’esempio con n = 8 e k = 6. La somma su A comporta in questo caso solo due tipi di addendo, poiché le sole sequenze distinte di 6 numeri non nulli la cui somma sia 8 sono di due tipi:
a) cinque “1” e un “3” → 6 possibilità distinte: 311111, 131111, 113111, ….
b) quattro “1” e due “2” → 15 possibilità distinte: 221111, 212111, ….
Le permutazioni del tipo a) sono in numero di (8!)/(3!) = 6720, che va quindi moltiplicato per 6 (numero delle possibili sequenze di tipo a), ottenendo 40320; le permutazioni del tipo b) sono in numero di (8!)/(2!2!) = 10080, che va moltiplicato per 15 (numero delle possibili sequenze di tipo b), ottenendo 151200. Sommando, si ottiene il valore cercato:
40320 + 151200 = 191520.
Massimo Bergamini