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

Consideriamo ora il problema:

Quanti sono i risultati di 5 estrazioni ordinate, un oggetto alla volta, da un'urna che ne contiene 10 - tutti diversi tra loro- quando gli oggetti vengano reinseriti nell'urna dopo la loro estrazione ?

Supponendo che gli oggetti siano contrassegnati ad esempio con lettere

{a,b,c,d,e,f,g,h,i,j}® urna

per un totale di elementi pari a

dim(urna)
			10

è possibile simulare ogni risultato delle 5 estrazioni senza reinserimento con

seq(urna[rand(10)],i,1,5)
			{e,f,c,e,h}

Applicando ancora il primo criterio per contare si può capire che la risposta è 10⁵.

In questi casi si parla di disposizioni con ripetizione di n elementi k alla volta, il cui numero è n^k.

Altri esempi:

1. quante liste di data lunghezza k che si possono realizzare con un certo numero di simboli n, sono n^k;
2. quante sono le funzioni f : S_k ® S_n dove card(S_k)=k e card(S_n)=n
3. in quanti modi diversi si possono sistemare n oggetti in k cassetti ciascuno dei quali li può contenere anche tutti. Ad esempio f : posti={1,2,3,…,k}® oggetti.
4. quante sono le diverse possibili colonne di una schedina del totocalcio?
5. Quante sono i possibili esiti delle votazioni nominali di n candidati da parte di k individui?
6. Quanti numeri naturali di k cifre si possono formare in un sistema di numerazione posizionale di base n? (n-1)n^k-1
7. Quante opere di lunghezza k, più o meno sensate, si possono scrivere con una macchina da scrivere che dispone di n caratteri?

Un caso particolare interessante è quello in cui S_n={0,1}; in questo caso, interpretando il simbolo 1 come ‘ scelta dell’elemento che gli corrisponde ’ e il simbolo 0 come ‘non scelta …’, le funzioni f : S_k ® {0,1} sono in evidente corrispondenze biunivoca con i sottoinsiemi di S_k. Il loro numero è dunque 2^k.

Per costruire in ordine lessicografico le disposizioni con ripetizioni di n elementi presi k alla volta si può ricorrere alla numerazione in base n.

Una utile function con argomenti i simboli che rappresentano gli elementi dell’urna, il numero k di disposizioni e il numerro di disposizione richiesto nell’ordinamento lessicografico, può fornire risultati come i seguenti:

dispRip({a,b,c,d,e},3,4)
				{a,a,d}
dispRip({a,b,c,d,e},3,124)
				{e,e,d}

Il codice della function potrà essere il seguente:

dispRip(lst.k,nOrd)
Func
Local nn, num
Dim(lst)® nn
If  n< nn^k Then
	InBase(lst,nOrd-1)® num<
	Return augment(seq(lst[1],i,1,dim(num)),num)
EndIf
EndFunc

Si appoggia a una function per trasformare un numero in base dieci in una qualunque altra base di cui siano date le cifre

InBase(cifre,n)
Func
Local bb, num
Dim(cifre)® bb
{}® num
While floor(nn/bb)>0
	augment({cifre[mod(nn,bb)+1]}, num)® num
	floor(nn/bb)® nn
EndWhile
augment({cifre[mod(nn,bb)+1]}, num)® num
Return num
EndFunc

Si possono costruire le disposizioni con ripetizione anche algebricamente, ad esempio i termini di

Expand((a1+b1+d1)(a2+b2+d2)(a3+b3+d3)(a4+b4+d4))

producono i risultati di 4 estrazioni dall’urna contenente a, b, d se si interpreta ad es il termine a1a2b3a4 come il risultato in cui è uscito a nella 1^a, 2^a e 4^a estrazione e b nella 3^a. Invece

Expand((a+b+d)(a+b+d)(a+b+d)(a+b+d))

Non fa differenza nell’ordine delle estrazioni ma fornisce ugualmente qualche informazione; ad esempio il termine 4a³b mi dice sono quattro le estrazioni in cui è uscito 3 volte a e una volta b.

Per contarle è sufficiente porre a=b=d=1 ottenendo 3⁴.

Si consideri ora il problema:

Una simulazione si può realizzare esattamente come per le disposizioni semplici, senza ripetizioni, da un’urna rappresentata da una lista {a,a,a,a,a,a,b,b,b,b}.

Contare tutte le possibilità in questo caso non è difficile pensando alle disposizioni con ripetizioni di due oggetti a e b presi 5 alla volta e che solo la disposizione bbbbb è impossibile. Ma questa riflessione non si appoggia a un metodo e ci si può facilmente convincere che nella sua forma più generale il problema di contare il numero delle possibili estrazioni di k oggetti in un'urna di n oggetti raggruppabili in n₁, n₂,…,n_h gruppi ciascuno formato da oggetti identici, con n₁+n₂+…n_h=n, non è di facile soluzione.

Se invece il numero delle estrazioni esaurisce tutti gli oggetti ci si può servire di una

In tal modo si può contare che sono i diversi modi di estrarre uno a uno, tenendo conto dell’ordine, tutti gli oggetti di un’urna che ne contiene 6 indistinguibili tra loro e i rimanenti anch’essi indistinguibili tra loro.

In generale le permutazioni di n oggetti in cui il primo è ripetuto k₁ volte, il secondo k₂ volte, …l’ultimo k_n volte è

Si tratta anche del problema di contare il numero di partizioni ordinate di un insieme, cioè del numero di modi in cui un insieme di n elementi può essere suddiviso in k sottinsiemi in modo che il primo ne contenga n₁, il secondo n₂, l’ultimo n_k. La risposta è

Si tratta anche del problema di contare il numero di anagrammi, con significato o meno, di una parola. Ad esempio volendo fare un anagramma della parola ‘pippo’ occorre tener presente che ciascun elemento come ‘pippo’ stesso, può essere ottenuto permutando tra loro le tre lettere ‘p’; dunque i 5! Elementi che si contano considerando l’ordine, debbono essere divisi per 3!.

Altri esempi:

1. In quanti modi si possono estrarre da un'urna, contenente n oggetti diversi, prima n₁ oggetti insieme, poi n₂ oggetti insieme, ... infine n_k oggetti insieme, con n₁+n₂+…n_h=n ?
2. In quanti modi n oggetti diversi possono essere poste in k scatole, affinché la prima ne contenga n₁, la seconda n₂, l’ultima n_k ?
3. In quanti modi n oggetti diversi possono essere ripartiti tra k persone in modo che n₁ oggetti vadano alla prima persona, poi n₂ oggetti vadano alla seconda, ... infine n_k oggetti vadano all'ultima, con n₁+n₂+…n_h=n ?