<< pagina principale < ······················ << articoli < ······················ << analisi combinatoria < ······················

Analisi Combinatoria

con la TI-92

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

Disposizioni e Permutazioni

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

Ad esempio, supponendo che gli oggetti siano rappresentati da lettere,

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

si può simulare ogni singola estrazione

rand(dim(urna))
urna[ans(1)]

salvo poi aggiornare il contenuto dell’urna

augment(left(urna,ans(2)-1),rigth(urna,dim(urna)-ans(2))® urna

oppure si può far uso di una function che ha come argomenti la lista di simboli per rappresentare gli oggetti dell’urna e il numero totale di estrazioni da effettuare

estrai(urnao,k)
Func
Local  ii, acaso, estr
urnao® urna
{}® estr
For ii,1,k
	rand(dim(urna))® acaso
	augment(estr,{urna[acaso]})® estr
	augment(left(urna,acaso-1),rigth(urna,dim(urna)-acaso)®urna
EndFor
Return estr
EndFunc

Il numero di risultati diversi possono essere contati a partire dalla sequenza

Seq(i,i,10,5,-1)
			{10,9,8,7,6}

che rappresenta il numero delle diverse possibilità alla prima estrazione, poi alla seconda estrazione dopo che un oggetto è già stato tolto dall'urna, poi alla terza estrazione dopo che due oggetti sono già stati tolti, e così via.

E' intuitivo comprendere che:

I regola per contare
Se gli elementi da contare si possono suddividere in n₁ raggruppamenti ciascuno dei quali può a sua volta essere suddiviso in n₂ raggruppamenti ciascuno dei quali può a sua volta essere suddiviso in n₃ raggruppamenti e così via, allora il numero complessivo di elementi è

n = n₁ · n₂ · n₃ · ...

Ovvero: se l'elemento generico può essere individuato attraverso una sequenza di scelte, tra n₁ diverse possibilità la prima, e poi, effettuata la prima scelta, tra n₂ diverse possibilità la seconda, e poi, effettuata la seconda scelta, tra n₃ diverse possibilità la terza, e così via

Perciò:

Product(ans(1))
			30240

cioè il prodotto 10·9·8·7·6, conta il numero totale di risultati, di tutte le possibili serie di 5 estrazioni, senza reinserimento, da un’urna che contiene inizialmente 10 oggetti..

In generale si può definire la funzione

Product(Seq(i,i,,n,n-k+1,-1)) ® nDs(n,k)

per risolvere il problema quando l'urna contiene n oggetti e le estrazioni sono k.

Queste diversi risultati si dicono anche disposizioni di n oggetti presi k alla volta e la funzione nDs(n,k) ne conta il numero: n·(n- 1)·(n- 2)· … ·(n- k+2)·(n- k+1)

Per esempio

nDs(10,5)	
			30240

La Ti-92 ha già, predefinita, la function nPr(n,k).

Per esempio

nPr(10,5)
			30240

Altri problemi che si risolvono allo stesso modo:

Quanti sono i modi di inserire k oggetti distinguibili in n scatole (n £ k) distinguibili che contengono al massimo un oggetto solo?

Quanti sono i modi di inserire k oggetti distinguibili in n scatole (n > k) distinguibili che contengono al massimo un oggetto solo?

Quante sono le funzioni iniettive da un insieme di k elementi a un insieme di n elementi ( n³ k)?

Quante sono le parole di lunghezza k, senza ripetizioni, si possono formare a partire da un alfabeto di n lettere?

Quanti elenchi ordinati di lunghezza k si possono fare con n nomi diversi?

In quanti modi diversi si possono costruire pile di altezza n con k pedine distinguibili?

Quante configurazioni si possono fare con n particelle in k stati esclusivi?

Quando k=n si parla di permutazioni. Dunque le permutazioni sono le disposizioni di n oggetti presi n alla volta. Il loro numero si indica con n! (si legge n fattoriale).

Ad esempio si possono considerare i problemi:

Quanti sono i modi di inserire n oggetti distinguibili in n scatole distinguibili ciascuna contenente al massimo un oggetto solo?

Quante sono le funzioni biunivoche da un insieme di n elementi in se stesso?

Quanti sono gli anagrammi anche privi di senso di parole di lunghezza n senza doppie?

Quanti sono i diversi rimescolamenti di un mazzo di carte da tresette?

Si osservi che:

Quindi nDs(n,k) = n!/(n- k)!

Diverso, e più complesso, è il problema di generare le diverse disposizioni.

Per iniziare consideriamo le permutazioni.

Possiamo considerare il seguente algoritmo per costruire, a partire da un data permutazione di una sequenza di numeri diversi, quella successiva nell'ordine "alfabetico" (o meglio lessicografico).

Detta k₁ , k₂ , k₃ , …, k_n-1 , k_n la sequenza di numeri:

trovare il più grande i tale che k_i < k_i+1;
trovare il più grande j tale che k_i < k_j;
scambiare k_i con k_j;
invertire l'ordine degli elementi della sequenza che ora seguono k_i.

Ad esempio ecco la traccia di esecuzione dell'algoritmo nel caso della sequenza 3142

i=2 con ki=1

j=4 con kj=2

3214

3214.

Possiamo creare ora una function che, data una lista i cui elementi sono numeri, costruisca la lista seguente nell'ordine lessicografico oppure restituisca false nel caso sia già stata raggiunta l’ultima.

permSucc(lst)
Func
Local nn, ii, jj, kk
dim(lst)® nn
nn-1® ii
While lst[ii]³lst[ii+1]
	ii-1®ii
	If ii=0 Then
		Return false
		Exit
	EndIf
EndWhile
nn®jj
While lst[ii]³lst[jj]
	jj-1® jj
EndWhile
lst[jj] ® kk
lst[ii] ® lst[jj]
1® jj
While ii+jj<nn-jj+1
	lst[nn-jj+1] ® kk
	lst[ii+jj] ® lst[nn- jj+1]
	kk® lst[ii+jj]
	jj+1® jj
EndWhile
Return lst
EndFunc

oppure un function che dato il numero degli oggetti, rappresentati dalla lista dei primi numeri naturali, costruisce la lista di tutte le sue permutazioni (cioè una matrice n colonne x n! righe)

perm(nn)
Func
Local lst, perm<
seq(k, k, 1,n)® lst
lst® perm
permSucc(lst) ® lst
While lst≠false
	augment(perm,lst) ® perm
	permSucc(lst) ® lst
EndWhile
Return list►mat(perm,n)
EndFunc

Per le disposizioni possiamo creare ad esempio una function che, avente per argomenti una lista lunga k di simboli dell’attuale disposizione e quella, ordinata, dei simboli esclusi da quella, costruisca la lista successiva alla prima nell'ordine lessicografico

dispSucc(lst,lstR)
Func
Local kk, hh, ii, jj
dim(lst)® kk
dim(lstR)® hh
kk® ii
hh® jj
while lst[ii]>lstR[jj]
	jj+1® jj
	lst[ii]® lstrR[jj]
	ii- 1® ii
	If ii=0 Then
		Exit
	EndIf
EndWhile
If ii>0 Then
	While lst[ii]<lstR[jj]
		lstr[jj]® lstr[jj+1]
		jj-1® jj
		If jj=0 Then
			Exit
		EndIf
	EndWhile
	lst[ii]® lstR[jj+1]
	lstR[jj+2]®lst[ii]
	1® jj
	While ii+jj£kk
		lstR[jj]® lst[ii+jj]
		jj+1® jj
	EndWhile
EndIf
Return lst
EndFunc

Ad esempio

dispSucc({3,5,4},{1,2})
				{4,1,2}
dispSucc({4,1,2},{3,5})
				{4,1,3}

Naturalmenbte vi sono altri modi di ordinare le permutazioni, diversi dall'ordine lessicografico; si possono approfondire ad esempio su [Page-Wilson]

Un problema interessante è anche quello di individuare la i-esima permutazione nell'ordine lessicografico

iPerm(nn,kk)
Func
Local lst0, lst, qq, cc, ii,jj
Seq(h,h,1,nn) ®lst0
Lst0®lst
(n-1)! ®qq
For jj,1.nn-1
	Floor((kk-1)/qq)+1®cc
	Lst0[cc] ®lst[jj]
	For ii,cc,nn-jj
		Lst0[ii+1] ®lst0[ii]
	EndFor
	kk-qq*(cc-1) ®kk
	If jj=nn-1 Then
		Lst0[1] ®lst[nn]
	Else
		Floor(qq/(nn-jj)) ®qq
	EndIf
EndFor
Return lst
EndFunc

Un problema interessante è anche quello produrre una permutazione casuale - un mescolamento-

Diversi metodi:

per i da n a 2 scambia elem(i) con elem(acaso da 1 a i-1)
per i da 1 a caso da 1 a 100*n°elem prendi due posizioni a caso e scambia gli elem con quelle posizioni
per i da 1 a caso da 1 a 100*n°elem prendi due posizioni a caso k1 e k2 e poni l'elem(k1) tra elem(k2-1) e elem(k2)
….

Qual è il più efficiente?

Ad esempio si consideri la seguente function il cui argomento è una lista di numeri:

permCas(lst)
Func
Local nn, pcas, lst0
dim(lst) ® nn
If nn>1 Then
	rand(nn) ®pcas
	permCas(augment(left(lst,pcas-1),right(lst,nn-pcas))) ® lst0
	Return  augment(lst[pcas],lst0)
Else
	Return lst
EndIf
EndFunc