di Roberto Ricci, Liceo Scientifico "A.Righi", Bologna

Consideriamo il problema:

In quanti modi si possono effettuare 5 estrazioni, una alla volta, da un'urna che contiene 10 oggetti - tutti diversi tra loro - ogni volta reinsererendo l'oggetto estratto nell'urna, senza poi tenere conto dell'ordine con cui sono stati estratti?

I diversi modi possono essere rappresentati da (k₁, k₂, ..., k₁₀) dove k₁ rappresenta quante volte è uscito il primo oggetto, k₂ quante volte è uscito il secondo oggetto, ..., k₁₀ quante volte è uscito l'ultimo oggetto e naturalmente k₁+k₂+ ...+k₁₀ = 5.

Equivalentemente, sostituendo ciascun numero con una lista composta di altrettanti segni di spuntatura 'Ö', uno dei modi potrebbe essere rappresentato da (ÖÖ,,,Ö,,ÖÖ,,,,) per dire che il primo oggetto è uscito 2 volte, mai il 2° e e il 3°, 1 volta il 4° oggetto, ecc ...
Siccome ogni modo è una lista di 5 segni di spuntatura e 10-1 virgole, il numero totale di modi è dunque quello degli anagrammi (5+9)!/(5!9!)

In generale k estrazioni con reinbussolamento di n oggetti presentano C_n+k-1,k diverse possibili distribuzioni di frequenze

Consideriamo anche il problema:

La prima pedina può essere posta in una qualunque delle n caselle, la seconda pedina in una delle n-1 caselle rimaste vuote oppure nella casella già occupata, sopra o sotto la pedina già inserita, quindi in n- 1+2=n+1 modi diversi. Per la terza pedina sono possibili due casi, a seconda che le prime due siano finite nella stessa o in caselle diverse, in modo tale che si avranno n-1+3 oppure n-2+4, cioè, in ogni caso, n+2 scelte possibili. Non è difficile contare, con la prima regola, che le scelte possibili, sono n(n+1)(n+2)…(n+k- 1).

Dopo questo conteggio, si può passare a risolvere l'altro problema

Applicando la seconda regola per contare, è sufficiente dividere il numero precedente per k!, con un totale di

Tali problemi equivalgono anche ai seguenti:

1. In quanti modi diversi k oggetti indistinguibili si possono inserire in n scatole che possono contenere anche più di un oggetto, senza limite?
2. In quanti modi diversi si possono costruire n pile distinguibili con k pedine indistinguibili ?
3. In quanti modi diversi k quanti di energia si distribuiscono in n elementi di un sistema?
4. In quanti modi (configurazioni) k fotoni (in generale bosoni) si distribuiscono in n elementi di un sistema?
5. Quante sono le combinazioni con ripetizione di n lettere in stringhe di lunghezza k?
6. Quanti diversi raggruppamenti di k elementi si possono formare con n oggetti ciascuno ripetuto in almeno k copie identiche?
7. Quanti diversi istogrammi si possono costruire dati gli n possibili valori assunti entro una popolazione di k individui?
8. Quanti diversi risultati nelle elezioni di n candidati da parte di k elettori?
9. Quanti diversi risultati nel lancio n volte di un dado?
10. Quanti monomi di k° grado si possono fare con n lettere?

A proposito di questo ultimo caso, espandendo l’espressione

(a₁ + a₂ + a₃ + …+ a_k-1 + a_n )^k

si ottengono i diversi monomi di grado k, ciascuno a rappresentare le combinazioni con ripetizione dei k oggetti indistinguibili negli n contenitori a₁ , a₂ , a₃ , …, a_k-1 , a_n.

E' interessante inoltre che ad esempio il prodotto

(1+a+a²)(1+b+b²+b³)(1+c)

produce le combinazioni dei simboli a, a, b, b, b, c presi k alla volta con k=0,1, …, 6

mentre poi il prodotto

(1+x+x²)(1+x+x²+x³)(1+x)

esprime quante sono, delle precedenti combinazioni, quelle con i simboli presi k alla volta con k=0,1, …, 6; sono rispettivamente:

1, 3, 5, 6, 5, 3, 1.

Anche il prodotto

(1+a+a²)( b²+b³)(1+c)

consente di trovare qualcosa di interessante: quali sono le combinazioni con almeno due b.

Il prodotto

(1+a+a²)( b+b³)(1+c)

consente invece di trovare le combinazioni con un numero dispari di b.

In generale, dunque, i termini del prodotto

(1 + a₁ + … +a₁^k1)· (1 + a₂ + … +a₂^k2) … (1 + a_n + … +a_n^kn)

cioè i monomi del tipo a₁ⁱ¹·a₂ⁱ²· … ·a_nⁱⁿ rappresentano una particolare combinazione degli elementi a₁, a₂ ,… , a_n disponibili rispettivamente in k₁, k₂ ,… , k_n copie, presi i₁ + i₂ + … + i_n alla volta.

Invece i monomi che costituiscono i termini dello sviluppo del prodotto

(1 + x + … +x^k1)· (1 + x + … +x^k2) … (1 + x + … +x^kn)

cioè i monomi del tipo c·x^k informano che ci sono c combinazioni degli elementi a₁ , a₂ ,… , a_n disponibili rispettivamente in k₁, k₂ ,… , k_n copie, presi k alla volta.

In particolare se i k_i sono uguali si considerano i prodotti (1 + a + … +a^k)ⁿ; per k=1 i coefficienti formano, al variare di n, righe del triangolo di Pascal-Tartaglia; negli altri casi si ottengono generalizzazioni di questo triangolo. Tali coefficienti si possono ottenere anche con il metodo seguente, applicato ad esempio per k=2:

{1}
				{1}
tritar2(ans(1))
				{1 1 1}
tritar2(ans(1))
				{1 2 3 2 1}
tritar2(ans(1))
				{1 3 6 7 6 3 1}
tritar2(ans(1))
				{1 4 10 16 19 16 10 4 1}

Tritar2(ll)
Func
	Local ll1,ll2, ll3
	augment({0,0},ll)! ll1
	augment( {0}, augment(ll,{0}) )! ll2
	augment(ll,{0,0})! ll3
	Return ll1 + ll2 + ll3
EndFunc

Si possono considerare anche combinazioni con ripetizione di n oggetti, ciascuno con un numero illimitato di copie. Il loro numero può essere contato attraverso lo sviluppo di

(1 + x + x² + … )ⁿ = 1/(1-x)ⁿ.

I coefficienti dei monomi termini dello sviluppo sono i coefficienti binomiali nCr(n+k-1,k); nel triangolo di Pascal-Tartaglia formano le diagonali parallele ai lati - tra cui i numeri triangolari -.