Disposizione

Nel calcolo combinatorio, se n e k sono due insiemi interi positivi, si definisce disposizione di n elementi k a k (oppure di n elementi di classe k, oppure di n elementi presi k alla volta) ogni sottoinsieme ordinato di k oggetti estratti da un insieme di n oggetti, in cui i sottoinsiemi differiscono se presentano qualche elemento diverso o se presentano gli stessi elementi ma in ordine diverso. Talvolta, k viene chiamato numero di posti e la disposizione di n oggetti in k posti viene chiamata k-disposizione. Se si impone la condizione che in ogni sottoinsieme non sono ammessi elementi ripetuti si parla di disposizioni semplici altrimenti di disposizioni con ripetizione. Nel primo caso deve essere ovviamente k ≤ n.

Disposizioni semplici

Siano A un insieme finito di cardinalità k e B un insieme finito di cardinalità n, con 0 ≤ k ≤ n. Sia inoltre F_k l'insieme delle funzioni iniettive f: A → B.

Sia F_k-1 l'insieme delle funzioni iniettive da un sottoinsieme di A di cardinalità k–1 in B. Ciascuna di tali funzioni è un insieme di k-1 coppie (a,b), con a appartenente al sottoinsieme di A e b appartenente a B, tali che ciascun a e ciascun b compaiano in una sola di esse.

Sia |F_k-1| il numero di tali funzioni. Il numero delle funzioni iniettive da A in B si ottiene aggiungendo, per ciascuna funzione, il numero delle coppie (a,b) in cui a e b non siano già presenti in alcuna coppia. Vi è un solo a, ma vi sono n – (k-1) elementi b, ovvero n – (k-1) nuove coppie. Si ha quindi la ricorrenza:

${\begin{aligned}|F_{k}|&=(n-k+1)|F_{n-1}|\\&=(n-k+1)(n-k+2)\cdots (n-1)|F_{1}|\\&=(n-k+1)(n-k+2)\cdots (n-1)(n)={\frac {n!}{(n-k)!}}\end{aligned}}$

essendo |F₁| = n, in quanto vi sono n coppie (a,b) in cui a sia fissato e b sia scelto tra gli n elementi di B.

Il numero delle funzioni iniettive da un insieme di cardinalità k in uno di cardinalità n si indica anche col simbolo:

$(n)_{k}={\frac {n!}{(n-k)!}}$

Nella terminologia combinatoria classica, il numero delle applicazioni iniettive da un insieme di cardinalità k in un insieme di cardinalità n viene detto numero delle disposizioni semplici di n oggetti presi k alla volta, o di classe k, e si indica con D_n,k.

Ad esempio, se n=5 e k=3 e come oggetti consideriamo le lettere A, B, C, D ed E, allora le disposizioni possibili sono le seguenti 5!/(5-3)! = 120/2 = 60:

ABC ABD ABE ACB ACD ACE ADB ADC ADE AEB AEC AED

BAC BAD BAE BCA BCD BCE BDA BDC BDE BEA BEC BED

CAB CAD CAE CBA CBD CBE CDA CDB CDE CEA CEB CED

DAB DAC DAE DBA DBC DBE DCA DCB DCE DEA DEB DEC

EAB EAC EAD EBA EBC EBD ECA ECB ECD EDA EDB EDC

Il risultato può essere ottenuto col seguente ragionamento: supponiamo di mettere in un sacchetto le lettere A, B, C, D ed E e di estrarne una a caso. La prima lettera estratta può essere indifferentemente una delle 5 e quindi abbiamo 5 possibilità di estrazione. Ora passiamo ad estrarre la seconda lettera: poiché nel sacchetto ne sono rimaste 4, abbiamo 4 possibilità di estrazione. A questo punto, nel sacchetto ne sono rimaste 3 ed avremo quindi, per la terza lettera, 3 possibilità di estrazione. Se moltiplichiamo tutte le possibilità fra loro, avremo 5×4×3 = 60 possibili gruppi.

Generalizzando, ogni volta che si estrae una lettera, il numero delle lettere che si possono estrarre diminuisce di uno; se nel sacchetto ci sono n lettere e vogliamo estrarne k avremo:

$D_{n,k}=n(n-1)(n-2)\cdots (n-k+1)$

ovvero un prodotto di k fattori pari a n diminuito di 0, 1, ..., (k-1). Moltiplicando e dividendo tale prodotto per (n-k)!, si ottiene la formula data sopra:

${\begin{aligned}D_{n,k}&=n(n-1)(n-2)\cdots (n-k+1)\\&={\frac {n(n-1)(n-2)\cdots (n-k+1)(n-k)(n-k-1)\cdots 1}{(n-k)(n-k-1)\cdots 1}}\\&={\frac {n!}{(n-k)!}}\end{aligned}}$

Infine si può notare che c'è una relazione tra le disposizioni e le permutazioni; infatti nel caso in cui k sia uguale a n si avrebbe:

$D_{n,n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}={\frac {n!}{1}}=n!$

cioè le permutazioni di n elementi.

Disposizioni con ripetizione

Una funzione da un insieme A in un insieme B può essere vista come un insieme di coppie (a,b) tale che vi siano tante coppie quante sono gli elementi a di A e che non vi sia alcun a presente in più di una coppia. Possono invece esservi nessuna o più coppie aventi, come secondo membro, un dato elemento b di B.

Dati un insieme A di cardinalità k ed un insieme B di cardinalità n, con n e k interi positivi, il numero delle funzioni da A in B è dato da n^k, in quanto ciascuna delle k coppie può avere come secondo membro uno qualsiasi degli n elementi di B. Ad esempio, il numero delle funzioni da un insieme di 2 elementi {a, b} in un insieme di 10 elementi {1,...,10} è 10², in quanto si hanno 10 coppie del tipo (a, x), dove x = 1,2,...,10, e per ciascuna di esse 10 coppie del tipo (b, x). Ciascuna delle funzioni cercate è costituita da una delle dieci coppie il cui primo elemento sia a e da una delle dieci il cui primo elemento sia b; il numero di tali funzioni è quindi dato dalla cardinalità del prodotto cartesiano dei due insiemi di dieci coppie: 10×10=10².

Nella terminologia combinatoria classica, il numero delle funzioni da un insieme di cardinalità k in uno di cardinalità n viene detto numero delle disposizioni con ripetizione di n oggetti k a k, o di classe k; a differenza delle disposizioni semplici, k può essere maggiore di n.

L'esempio sopra proposto può essere reinterpretato come segue. Dati 10 oggetti distinti, il numero delle presentazioni di 2 di tali elementi, anche non diversi tra loro, è 10²; in particolare, con le 10 cifre da 0 a 9 si possono comporre 100 numeri di due cifre: 00, 01, ..., 09, 10, 11, ..., 19, 20, 21, 22, ...., 99.

Analogamente, il numero delle possibili colonne del totocalcio, composte da quattordici pronostici scelti fra tre (1, X o 2), è pari a: 3¹⁴ = 4.782.969.

Bibliografia

• Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elementi di matematica discreta, Bologna, Zanichelli, 1988.
• Sheldon M. Ross, Calcolo delle probabilità, Milano, Apogeo, 2004.

Voci correlate

• Calcolo combinatorio
• Permutazione
• Combinazione

Altri progetti

Altri progetti

• Wikizionario

• Wikizionario contiene il lemma di dizionario «disposizione»