Nel calcolo combinatorio, dati due numeri interi non negativi e con , si definisce disposizione semplice di elementi di classe (o presi alla volta) ogni sottoinsieme ordinato di elementi distinti estratti da un insieme di elementi (distinti). Nel caso in cui risulti uguale a , ci si trova di fronte a una permutazione dell'insieme di partenza. Ne consegue che le permutazioni non sono altro che un caso particolare di disposizioni semplici. Talvolta viene chiamato "numero di posti" e la disposizione di elementi in posti viene chiamata "-disposizione".
Dati due numeri interi non negativi e , si definisce disposizione con ripetizione di elementi di classe (o presi alla volta) ogni sottoinsieme ordinato di elementi non necessariamente distinti estratti da un insieme di elementi (distinti). In questo caso quindi il numero di posti può anche essere superiore al numero di elementi .
Le disposizioni trovano applicazione anche nel calcolo della probabilità. In particolare, esse risultano determinanti ogniqualvolta l'ordine degli elementi sia rilevante ai fini dell'identificazione dell'evento, consentendo di quantificare rigorosamente la probabilità di eventi complessi sia nel caso di campionamenti senza rimpiazzo (disposizioni semplici), sia in contesti che prevedono la reiterabilità degli elementi medesimi (disposizioni con ripetizione).
Disposizioni semplici Il numero di disposizioni semplici, denotate con il simbolo di elementi a a è dato da:
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
Fra di esse troviamo 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 e le estrazioni da effettuare sono si nota che si parte con possibilità di estrazione per la prima lettera estratta, si scende a per la seconda lettera estratta e così via fino ad arrivare a per la -esima lettera estratta. Ripetendo il ragionamento fatto sopra si ha
cioè il prodotto di fattori, ciascuno uguale ad diminuito via via di Moltiplicando e dividendo tale prodotto per si ottiene la formula data sopra:
È 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 : al massimo possono essere effettuate 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 elementi a a 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à e per codominio un insieme di cardinalità
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.
Per fissare le idee supponiamo di considerare le funzioni iniettive di 1 elemento in 4 elementi: in totale saranno 4 tali funzioni, tutte rappresentate in figura 1. Indichiamo con |F1|=4 il numero totale di tali funzioni dove il pedice 1 sta a ricordare che il dominio è costituito da un solo elemento.
Le funzioni iniettive di 2 elementi in 4 elementi sono in totale 12: in figura 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 figura 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, escludendo la 2-A visto che ci stiamo limitando alle funzioni iniettive e che l'elemento A del codominio è già associato all'elemento 1 del dominio). Ciò porta il totale a 4x3=12. Indichiamo con |F2|=|F1|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.
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, escludendo 3-A e 3-B per rispettare l'iniettività). Ciò porta il totale a 12x2=24. Indichiamo con |F3|=|F2|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.
Generalizzando, siano un insieme finito di cardinalità e un insieme finito di cardinalità con Sia inoltre l'insieme delle funzioni iniettive Vale la seguente formula ricorsiva
essendo in generale in conformità con l'esempio sopra delle funzioni di 1 in 4 dove essendo nella fattispecie Siamo così giunti alla conclusione enunciata sopra che il numero di funzioni iniettive di un insieme di cardinalità in un insieme di cardinalità si identifica con quello delle disposizioni semplici di elementi a a
Il numero delle funzioni iniettive di un insieme di cardinalità in uno di cardinalità si indica anche col simbolo:
Esempi 1) Supponiamo di voler conoscere il numero totale dei possibili podi di una corsa a cui prendono parte 10 corridori. Poiché l'ordine di arrivo è importante bisognerà considerare le disposizioni (semplici poiché non ci può essere ripetitività essendo impossibile che uno stesso corridore risulti ad esempio contemporaneamente 1º e 2º classificato) anziché le combinazioni. In particolare bisognerà considerare le disposizioni di 10 elementi a 3 a 3. Avremo pertanto:
Quindi il podio potrà essere formato da 720 diversi raggruppamenti di corridori.
2) Considerando che il campionato di Serie A è costituito da 20 squadre, supponiamo di voler conoscere il numero totale di partite che si disputeranno in una stagione. Poiché due generiche squadre A e B si affronteranno sia nel girone di andata (A-B con A che gioca in casa) sia in quello di ritorno (B-A con A che gioca fuori casa) ciò equivale a dire che l'ordine è importante e che pertanto abbiamo a che fare con le disposizioni (semplici poiché non ci può essere ripetitività essendo impossibile che una squadra possa affrontare sé stessa) anziché le combinazioni. In particolare avremo:
Quindi in totale in una stagione si disputeranno 380 partite di Serie A.
Disposizioni con ripetizione Il numero di disposizioni con ripetizione, denotate con il simbolo di elementi a a è dato da:
Anche qui per dare una spiegazione di tale formula si può ricorrere all'"estrazione degli elementi" da un sacchetto oppure alle "funzioni".
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. Anche la terza lettera, infine, 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=43=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 e le estrazioni da effettuare sono si nota che, rimettendo ogni volta la lettera appena estratta nel sacchetto, si riparte con tutte le lettere a disposizione indipendentemente se si tratta della prima, seconda, terza estrazione e così via. Il numero di disposizioni con ripetizione è dato, come volevasi dimostrare, dal prodotto di per sé stesso volte da cui la formula: