Disposizione

Nel calcolo combinatorio, se n e k sono due numeri interi non negativi, si definisce disposizione di n elementi a k a k (oppure di n elementi di classe k, oppure di n elementi presi k alla volta) ogni sottoinsieme ordinato di k elementi estratti da un insieme di n elementi tale che i sottoinsiemi differiscono se presentano qualche elemento diverso oppure se presentano gli stessi elementi ma ordinati diversamente. Talvolta k viene chiamato numero di posti e la disposizione di n elementi in k posti viene chiamata k-disposizione.

Se nei sottoinsiemi non sono ammessi elementi ripetuti si parla di disposizioni semplici altrimenti di disposizioni con ripetizione: nel primo caso deve essere $k\leq n.$

Disposizioni semplici

Il numero di disposizioni semplici, denotate con il simbolo $D_{n,k},$ di $n$ elementi a $k$ a $k$ è pari a:

$D_{n,k}=n(n-1)(n-2)\cdot \cdot \cdot (n-k+1)={\frac {n!}{(n-k)!}}.$

Per dare una spiegazione di tale formula si può ricorrere all'estrazione degli elementi da un sacchetto oppure alle funzioni iniettive.

Estrazione degli elementi

Supponiamo di voler estrarre 3 elementi a partire da un insieme di 5 elementi: in altri termini supponiamo di voler considerare le disposizioni di 5 elementi a 3 a 3.

A tale proposito supponiamo di mettere in un sacchetto le 5 lettere A, B, C, D ed E e di volerne estrarre 3 a caso. La prima lettera che andremo ad estrarre sarà indifferentemente una delle 5 e quindi avremo 5 possibilità di estrazione. La seconda lettera che andremo ad estrarre sarà una delle 4 rimaste nel sacchetto e quindi avremo 4 possibilità di estrazione. La terza lettera infine che andremo ad estrarre sarà una delle 3 rimaste nel sacchetto e quindi avremo 3 possibilità di estrazione. Se moltiplichiamo tutte le possibilità fra loro avremo 5x4x3 = 60 possibili gruppi. Tali gruppi sono tutti quelli che è possibile considerare prendendo 3 elementi dall'insieme di 5 elementi e comprendono anche i gruppi costituiti dagli stessi elementi ma ordinati diversamente: si tratta evidentemente di tutte le 60 possibili disposizioni ottenibili raggruppando 5 elementi a 3 a 3. Le 60 disposizioni sono riportate di seguito:

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

Tra di esse ritroviamo anche ABC, ACB, BAC, BCA, CAB e CBA: pur essendo disposizioni costituite dagli stessi elementi esse sono da considerarsi differenti perché ordinate diversamente in conformità alla stessa definizione di disposizione.

Generalizzando, se le lettere in totale sono n e le estrazioni da effettuare sono k, si nota che si parte con una probabilità n per la prima lettera estratta, si scende a n-1 per la seconda lettera estratta e così via fino ad arrivare a n-k+1 per la k-ma lettera estratta. Ripetendo il ragionamento fatto sopra avremo:

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

ovvero un prodotto di k fattori, ciascuno pari a n diminuito via via 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}}$

È da notare infine che quando viene estratta una lettera dal sacchetto, quest'ultima non viene rimessa dentro: questo fatto garantisce che la stessa lettera non può essere estratta più volte e che quindi non ci possono essere elementi ripetuti nel sottoinsieme estratto in conformità alla definizione di disposizione semplice. L'esempio del sacchetto spiega anche perché deve risultare necessariamente k≤n: al massimo possono essere effettuate n estrazioni, dopodiché non rimangono altre lettere nel sacchetto da poter estrarre.

Funzioni iniettive

Oltre che ricorrendo all'estrazione delle lettere da un sacchetto, per ottenere il numero di disposizioni di n elementi a k a k si può ricorrere all'utilizzo delle funzioni iniettive e in particolare alla determinazione del numero totale di tutte le funzioni iniettive aventi per dominio un insieme di cardinalità k e per codominio un insieme di cardinalità n.

Una funzione iniettiva è una legge che associa a ogni elemento del dominio un differente elemento del codominio. Considerando il caso di un dominio e di un codominio costituiti da due insiemi di elementi, ciò significa che da ogni elemento del dominio parte una sola linea di associazione (questo fatto è sempre vero per la definizione stessa di funzione sia essa iniettiva, suriettiva o biiettiva) e che su ogni elemento del codominio arriva una sola linea di associazione. Nel caso di funzioni suriettive, fermo restando che da ogni elemento del dominio parte una sola linea, capita invece che su uno o più elementi del codominio arrivi più di una linea di associazione.

Differenza tra funzione iniettiva-suriettiva

Per fissare le idee supponiamo di considerare le funzioni iniettive di 1 elemento in 4 elementi: in totale saranno solo 4 tali funzioni rappresentate tutte nella fig. 1. Indichiamo con |F₁|=4 il numero totale di tali funzioni dove il pedice 1 sta a ricordare che il dominio è costituito da un solo elemento.

Fig. 1: funzioni di un elemento in un insieme di 4 elementi

Le funzioni iniettive di 2 elementi in 4 elementi sono in totale 12: in fig. 2 sono riportati due diversi esempi delle 12 funzioni possibili. Da notare che nel passaggio dalle funzioni iniettive di 1 in 4 a quelle di 2 in 4 si è passati da 4 funzioni possibili a 12 funzioni possibili: ciò si spiega con il fatto che a ciascuna delle funzioni di 1 in 4 (ad esempio la 1-A di fig. 1) è come se si fosse aggiunto un altro elemento al dominio (ad esempio l'elemento "2") e da questo è possibile far partire 3 diverse associazioni (2-B, 2-C e 2-D). Ciò porta il totale a 4x3=12. Indichiamo con |F₂|=|F₁|x(4-1)=4x3=12 il numero totale di tali funzioni dove il pedice 2 a primo membro e il pedice 1 a secondo membro stanno a ricordare che il dominio è costituito rispettivamente da due elementi e da un elemento conformemente alla nostra esposizione.

Fig. 2: esempi di funzioni iniettive di due elementi in un insieme di 4 elementi

Ripetendo il ragionamento, le funzioni iniettive di 3 in 4 elementi sono in totale 24: in figura 3 sono riportati due diversi esempi delle 24 funzioni possibili. Da notare che nel passaggio dalle funzioni iniettive di 2 in 4 a quelle di 3 in 4 si è passati da 12 funzioni possibili a 24 funzioni possibili: ciò si spiega con il fatto che a ciascuna delle funzioni di 2 in 4 (ad esempio la 1-A, 2-B di fig. 2) è come se si fosse aggiunto un altro elemento al dominio (ad esempio l'elemento "3") e da questo è possibile far partire 2 diverse associazioni (3-C e 3-D). Ciò porta il totale a 12x2=24. Indichiamo con |F₃|=|F₂|x(4-2)=12x2=24 il numero totale di tali funzioni dove il pedice 3 a primo membro e il pedice 2 a secondo membro stanno a ricordare che il dominio è costituito rispettivamente da tre elementi e da due elementi conformemente alla nostra esposizione.

Fig. 3: esempi di funzioni iniettive di tre elementi in un insieme di 4 elementi

Generalizzando, 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. Vale la seguente ricorrenza:

${\begin{aligned}|F_{k}|&=(n-k+1)|F_{k-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 in generale |F₁|=n in conformità con l'esempio sopra delle funzioni di 1 in 4 dove |F₁|=4 avendosi nella fattispecie n=4. Siamo così giunti alla conclusione enunciata sopra che il numero di funzioni iniettive di un insieme di cardinalità k in un insieme di cardinalità n si identifica con quello delle disposizioni semplici di n elementi a k a k.

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

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

Disposizioni con ripetizione

Il numero di disposizioni con ripetizione, denotate con il simbolo $D_{n,k}^{'},$ di $n$ elementi a $k$ a $k$ è:

$D_{n,k}^{'}=n^{k}.$

La formula si può ottenere usando la seguente formalizzazione. 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.

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.

Esempi

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².

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»