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$ è dato da:

$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 $n$ possibilità di estrazione 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$-esima lettera estratta. Ripetendo il ragionamento fatto sopra avremo

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

cioè il prodotto di $k$ fattori, ciascuno uguale ad $n$ diminuito via via di $0,1,\ldots ,(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\leq 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 figura 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") da cui è 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") da cui è 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\leq k\leq n.$ Sia inoltre $F_{k}$ l'insieme delle funzioni iniettive $f\colon A\to 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_{1}|=n$ in conformità con l'esempio sopra delle funzioni di 1 in 4 dove $|F_{1}|=4$ essendo 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$ è dato da:

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

Anche qui per dare una spiegazione di tale formula si può ricorrere all'estrazione degli elementi da un sacchetto oppure alle funzioni iniettive e suriettive.

Estrazione degli elementi

Supponiamo di voler estrarre 3 elementi a partire da un insieme di 4 elementi ma a differenza di prima facciamo in modo che gli elementi possano ripetersi: in altri termini si vogliono trovare le disposizioni con ripetizione di 4 elementi a 3 a 3.

A tale proposito supponiamo di mettere in un sacchetto le 4 lettere A, B, C e D e di volerne estrarre 3 a caso. La prima lettera che andremo ad estrarre sarà indifferentemente una delle 4 e quindi avremo 4 possibilità di estrazione. Ora però, prima di procedere all'estrazione della seconda lettera, rimettiamo nel sacchetto la lettera che abbiamo appena estratto. Anche la seconda lettera che andremo ad estrarre sarà indifferentemente una delle 4 e quindi avremo nuovamente 4 possibilità di estrazione: tra l'altro può capitare che la seconda lettera estratta sia la stessa della prima, che quindi ci sia la ripetitività, essendo ripartiti con tutte le lettere nel sacchetto. Ancora una volta rimettiamo nel sacchetto la lettera appena estratta. Infine, anche la terza lettera che andremo ad estrarre sarà indifferentemente una delle 4 e quindi avremo nuovamente 4 possibilità di estrazione. Se moltiplichiamo tutte le possibilità fra loro avremo 4x4x4=4³=64 possibili gruppi, vale a dire le 64 possibili disposizioni con ripetizione di 4 elementi presi a 3 a 3.

Tali disposizioni sono riportate di seguito:

AAA AAB AAC AAD ABA ABB ABC ABD

ACA ACB ACC ACD ADA ADB ADC ADD

BAA BAB BAC BAD BBA BBB BBC BBD

BCA BCB BCC BCD BDA BDB BDC BDD

CAA CAB CAC CAD CBA CBB CBC CBD

CCA CCB CCC CCD CDA CDB CDC CDD

DAA DAB DAC DAD DBA DBB DBC DBD

DCA DCB DCC DCD DDA DDB DDC DDD

Come si può vedere diversi gruppi presentano elementi ripetuti: per esempio, le disposizioni AAB e BAA sono considerate differenti in quanto pur avendo gli stessi elementi (la lettera A che si ripete due volte e la lettera B) esse sono ordinate diversamente.

Generalizzando, se le lettere sono $n$ e le estrazioni da effettuare sono $k,$ si nota che, avendo cura di rimettere la lettera estratta nel sacchetto, si riparte ogni volta con tutte le lettere nel sacchetto indipendentemente se si tratta della prima, seconda, terza estrazione e così via. Il numero di disposizioni con ripetizione è dato dal prodotto di $n$ per sé stesso $k$ volte, da cui la formula:

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

A differenza delle disposizioni semplici, nelle disposizioni con ripetizione non vale il vincolo $k\leq n$: poiché ogni volta si rimette nel sacchetto la lettera appena estratta, non c'è il rischio che esse si esauriscano come capita invece nelle disposizioni semplici in cui, dopo $n$ estrazioni, non rimangono nel sacchetto più lettere da poter estrarre.

Funzioni iniettive e suriettive

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

Per fissare le idee supponiamo di considerare le funzioni di 1 elemento in 4 elementi: poiché c'è una sola linea di associazione che parte dall'unico elemento presente nel dominio e poiché tale linea non può che finire in un unico elemento dei 4 presenti nel codominio, non si verificherà mai per questa condizione di avere a che fare con funzioni suriettive le quali, come detto sopra, richiedono che almeno un elemento del codominio sia interessato da almeno due linee di associazione. Pertanto anche nel caso delle disposizioni con ripetizione varrà la figura 1 essendo le funzioni di 1 in 4 sempre di tipo iniettivo. Quindi le disposizioni semplici di 4 elementi a 1 a 1 e quelle con ripetizione di 4 elementi a 1 a 1 si identificano fra di loro, anche perché è impossibile avere delle ripetizioni se si è in presenza di un solo elemento.

Passiamo ora a considerare le funzioni di 2 elementi in 4 elementi: la figura 4 illustra tutte le 16 funzioni di tale tipo, siano esse iniettive o suriettive. In particolare si può notare come la situazione di suriettività dia vita alla ripetitività degli elementi del codominio che contraddistingue a sua volta le disposizioni con ripetizione: ad esempio la (1) della figura 4 determina la disposizione AA mentre la (8) determina la disposizione BB.

Nel passaggio dalle funzioni di 1 elemento in 4 elementi a quella di 2 elementi in 4 elementi è come se al dominio avessimo aggiunto un altro elemento: a differenza del caso delle disposizioni semplici, ora nelle disposizioni con ripetizione consentiamo a questo secondo elemento di associarsi con uno qualunque dei 4 elementi del codominio anche con l'elemento del codominio già associato al primo elemento del dominio. Pertanto le 4 associazioni relative al primo elemento del dominio vanno moltiplicate per le 4 associazioni relative al secondo elemento del dominio ottenendo 4x4=16 che sono proprio il totale delle funzioni iniettive e suriettive di 2 elementi in 4 elementi.

Fig. 4: funzioni di 2 elementi in 4 elementi

Generalizzando, se con $A$ denotiamo un insieme finito di cardinalità $k$ e con $B$ un insieme finito di cardinalità $n,$ il numero totale di funzioni $f\colon A\to B,$ iniettive o suriettive che siano, sarà uguale a $n^{k}$ in conformità con la formula delle disposizioni con ripetizione che ci proponevamo di dimostrare:

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

Esempi

I numeri di due cifre (00, 01, ..., 09, 10, 11, ..., 19, 20, 21, 22, ...., 99) sono quelli che si ottengono dalle disposizioni con ripetizione di 10 elementi (i numeri da 0 a 9) presi a 2 a 2: quindi in totale sono 10²=100 come d'altronde si può verificare direttamente.

Il numero delle possibili colonne del totocalcio composte da tredici pronostici scelti fra tre elementi (1, X o 2) è uguale a 3¹³ = 1.594.323. In questo caso risulta $k>n$ essendo $k=13$ ed $n=3$ a conferma del fatto che nelle disposizioni con ripetizione il numero di posti $k$ può essere qualunque indipendentemente da $n.$

Permutazione: caso particolare di disposizione semplice

Si può notare che c'è una stretta correlazione tra le disposizioni semplici e le permutazioni. Infatti nel caso in cui $k$ sia uguale a $n$ si ha:

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

che coincide con il numero di permutazioni di $n$ elementi.

D'altronde ciò è ovvio se si ricorre all'esempio dell'estrazione delle lettere da un sacchetto: le permutazioni possono essere viste come le estrazioni delle lettere con la condizione che vengano effettuate tante estrazioni quante sono le lettere stesse, fino ad esaurimento, senza che ce ne rimangano delle altre nel sacchetto.

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»