Le combinazioni semplici contano i modi di scegliere k elementi distinti tra n. Ma molte situazioni reali permettono di prendere lo stesso elemento più volte: comprare 10 gelati scegliendo tra 4 gusti, distribuire 20 server identici su 3 data center, comporre un ordine di 12 pezzi da un catalogo di 5 articoli. Per questi casi esiste un metodo di conteggio elegante, detto delle stelle e barre, che trasforma il problema in una semplice combinazione.
Il problema tipo
In quanti modi si possono scegliere 10 gelati tra 4 gusti, se conta solo quanti gelati di ciascun gusto si prendono e non l'ordine?
Una scelta è descritta da quattro numeri non negativi x₁, x₂, x₃, x₄ con
x₁ + x₂ + x₃ + x₄ = 10
Quindi la domanda equivale a: quante sono le soluzioni intere non negative di questa equazione?
Stelle e barre
Rappresentiamo ogni gelato con una stella ★ e separiamo i gusti con 3 barre |. Una scelta diventa una sequenza di 10 stelle e 3 barre:
★★★|★★||★★★★★
Questa sequenza significa: 3 gelati del primo gusto, 2 del secondo, 0 del terzo, 5 del quarto. Ogni sequenza di 10 stelle e 3 barre corrisponde esattamente a una scelta, e viceversa: è una biiezione.
Contare le sequenze è facile. Sono lunghe 13 simboli, e basta decidere in quali 3 posizioni mettere le barre:
C(13, 3) = 286
La formula generale
Il numero di modi di scegliere k oggetti da n tipi, con ripetizione e senza ordine, è:
C(n + k − 1, k) = C(n + k − 1, n − 1)
Le stelle sono k, le barre sono n − 1 (servono n − 1 separatori per n tipi), e si sceglie la posizione delle barre, o equivalentemente delle stelle.
Vincoli minimi
Se ogni gusto deve essere preso almeno una volta, si assegna prima un gelato a ciascun gusto. Restano 10 − 4 = 6 gelati da distribuire liberamente su 4 gusti:
C(6 + 3, 3) = C(9, 3) = 84
In generale, con il vincolo xᵢ ≥ 1, le soluzioni di x₁ + … + xₙ = k sono C(k − 1, n − 1). Si può vederlo anche direttamente: tra le k stelle in fila ci sono k − 1 spazi, e bisogna sceglierne n − 1 in cui mettere una barra, al massimo una per spazio.
Vincoli massimi
I vincoli del tipo xᵢ ≤ m sono più delicati e si gestiscono con il principio di inclusione-esclusione.
Esempio: quante soluzioni ha x₁ + x₂ + x₃ = 10 con 0 ≤ xᵢ ≤ 4?
- Senza vincoli: C(12, 2) = 66.
- Soluzioni con x₁ ≥ 5: si pone y₁ = x₁ − 5 e si ottiene y₁ + x₂ + x₃ = 5, con C(7, 2) = 21 soluzioni. Lo stesso per x₂ e x₃: in totale 3 · 21 = 63.
- Soluzioni con due variabili ≥ 5: per esempio x₁, x₂ ≥ 5 dà y₁ + y₂ + x₃ = 0, con 1 soluzione. Le coppie sono 3, in totale 3.
- Tre variabili ≥ 5 richiederebbero una somma di almeno 15: impossibile.
Risultato: 66 − 63 + 3 = 6. Verifica diretta: le soluzioni sono le permutazioni di (4, 4, 2) e di (4, 3, 3), cioè 3 + 3 = 6.
Permutazioni con ripetizione
Un problema diverso ma imparentato: quanti anagrammi distinti ha una parola con lettere ripetute? Qui l'ordine conta, ma oggetti uguali non si distinguono.
Per la parola MISSISSIPPI, di 11 lettere con M una volta, I quattro volte, S quattro volte e P due volte, gli anagrammi sono:
11! / (1! · 4! · 4! · 2!) = 34.650
Si divide il numero di permutazioni di 11 oggetti per i modi di permutare tra loro le lettere uguali, che non producono parole nuove. Questo numero si chiama coefficiente multinomiale.
Un riepilogo
| Situazione | Ordine | Ripetizione | Conteggio |
|---|---|---|---|
| Stringhe di lunghezza k su n simboli | sì | sì | nᵏ |
| Sottoinsiemi di k elementi | no | no | C(n, k) |
| Multinsiemi di k elementi da n tipi | no | sì | C(n + k − 1, k) |
| Anagrammi con ripetizioni | sì | fissata | n! / (k₁! … kᵣ!) |
Dove serve in informatica
- Distribuzione di risorse identiche: il numero di modi di ripartire k unità di capacità tra n servizi è C(n + k − 1, n − 1). Serve a capire quando una ricerca esaustiva è praticabile.
- Istogrammi e conteggi: il numero di possibili vettori di conteggio di k osservazioni in n categorie è proprio il numero delle combinazioni con ripetizione.
Un controllo veloce con il codice, per piccoli valori, conferma sempre il ragionamento:
from itertools import combinations_with_replacement
assert len(list(combinations_with_replacement(range(4), 10))) == 286
In sintesi
- Scegliere k oggetti da n tipi con ripetizione equivale a contare le soluzioni di x₁ + … + xₙ = k.
- Con stelle e barre le soluzioni non negative sono C(n + k − 1, k).
- I vincoli minimi si gestiscono sottraendo in anticipo; quelli massimi con inclusione-esclusione.
- Gli anagrammi con lettere ripetute si contano con il coefficiente multinomiale.
- Verificate sempre le formule su piccoli casi con una enumerazione.
