View source for Combinazione

{{Nota disambigua}}
{{NN|matematica|dicembre 2020}}
[[File:Combinations without repetition; 5 choose 3.svg|thumb|alt=Sottoinsiemi da 3 elementi di un insieme di 5 elementi|Sottoinsiemi da 3 elementi di un insieme di 5 elementi]]
Nel [[calcolo combinatorio]], dati <math>n</math> e <math>k</math> due [[Numero intero|interi]] non negativi, si definisce '''combinazione''' di un insieme di <math>n</math> elementi ''presi'' <math>k</math> ''alla volta'' (oppure ''di classe'' <math>k</math>, o a <math>k</math> a <math>k</math>) ogni [[multiinsieme]] di <math>k</math> elementi che appartengono all'insieme (detti anche "''estratti''" ''dall'insieme'') di quegli <math>n</math> elementi. Una combinazione è detta [[Combinazione#Combinazioni semplici|semplice]], o ''senza ripetizioni'', [[se e solo se]] ogni suo membro ha molteplicità 1 (ossia non ci sono elementi che si ripetono), e [[Combinazione#Combinazioni con ripetizione|combinazione con ripetizione]] altrimenti. Una combinazione semplice di <math>n</math> elementi di classe <math>k</math> è perciò equivalente a un [[sottoinsieme]], di [[cardinalità]] <math>k</math>, dell'insieme degli <math>n</math> elementi dai quali è estratta, dunque in tal caso <math>k \le n</math>.
A volte, per questi motivi, se si vuole specificare che una combinazione di <math>n</math> elementi di classe <math>k</math> è una combinazione semplice, viene direttamente chiamata un <math>k</math>-insieme di (un insieme di) <math>n</math> elementi; invece una combinazione con ripetizioni è chiamata un <math>k</math>-multiinsieme di (un insieme di) <math>n</math> elementi.<ref>A volte l'utilizzo di questa terminologia può specificare esplicitamente che la combinazione è una combinazione con ripetizioni, ossia che il (sotto-)multiinsieme non è un insieme, mentre in altri casi è un sinonimo di combinazione in generale, con o senza ripetizioni.</ref>

In entrambi i casi, estrazioni di elementi uguali a meno dell'ordine generano comunque la stessa combinazione. Ad esempio, prendendo alcune combinazioni di classe 3 dell'insieme {''p,q,r,s,t''}, le estrazioni rappresentate dalle terne ordinate (''p,r,s''), (''p,s,r''), (''r,p,s''), (''s,p,r''), (''r,s,p'') e (''s,r,p'') indicano ''la stessa combinazione'' in quanto formate dagli stessi elementi, cioè corrispondono tutte all'insieme (non ordinato per definizione) {''p,r,s''} sottoinsieme di {''p,q,r,s,t''}. D'altra parte, (''p,r,s'') e (''s,r,q'') indicano ''due diverse combinazioni'' perché corrispondono agli insiemi {''p,r,s''} e {''s,r,q''} che differiscono per almeno un elemento, e l'estrazione (''p,p,r,s'') identifica una combinazione diversa da (''r,p,s,s'') perché le molteplicità di ''p'' e ''s'' differiscono, mentre identifica la stessa combinazione di (''p,r,s,p'') perché formate dagli stessi elementi con le stesse molteplicità.

== Combinazioni semplici ==
Dato un [[insieme]] ''A'' di [[cardinalità]] ''n'', il numero dei sottoinsiemi di ''A'' di cardinalità ''k'' ≤ ''n'', vale a dire le combinazioni di ''n'' elementi presi a ''k'' a ''k'', si ottiene dividendo il numero di tutti i possibili sottoinsiemi ordinati di cardinalità ''k'' in ''A'' ([[Disposizione|disposizioni]] di ''n'' elementi di classe ''k'') per il numero delle [[Permutazione|permutazioni]] di ''k'' elementi:

:<math>C_{n,k}=\frac{D_{n,k}}{P_k}=\frac{\frac{n!}{(n-k)!}}{k!}=\frac{n!}{(n-k)!k!}={n \choose k}.</math>

Il simbolo <math>{n \choose k}</math> viene detto [[coefficiente binomiale]].

=== Giustificazione della formula ===
Si considerino i sottoinsiemi di cardinalità 4 dell'insieme {''a,b,c,d,e,f''}. Avremo che:

:<math>C_{6,4}=\frac{6!}{(6-4)!4!}=\frac{6!}{2!4!}=\frac{720}{2\cdot 24}=15.</math>

Nella fattispecie, i 15 gruppi sono:

:abcd, abce, abcf, abde, abdf, abef, acde, 
:acdf, acef, adef, bcde, bcdf, bcef, bdef, cdef.

Il risultato può essere ottenuto col seguente ragionamento. Immaginiamo di mettere in un sacchetto le 6 lettere ''a,b,c,d,e,f'' ed estraiamo a caso la prima che può essere indifferentemente una delle 6: abbiamo quindi 6 possibilità di estrazione. Ora passiamo ad estrarre la seconda lettera: poiché nel sacchetto ne sono rimaste 5, abbiamo 5 possibilità di estrazione. Passiamo quindi ad estrarre la terza lettera: poiché nel sacchetto ne sono rimaste 4, abbiamo 4 possibilità di estrazione. Infine, reiterando ancora il ragionamento, quando andremo ad estrarre la quarta lettera ne saranno rimaste 3 nel sacchetto e avremo quindi 3 possibilità di estrazione. Se moltiplichiamo tutte le possibilità fra loro, avremo 6×5×4×3 = 360 possibili gruppi.

Il valore ottenuto di 360 è, in realtà, il numero delle [[Disposizione|disposizioni semplici]] di 6 oggetti di classe 4 nelle quali ''l'ordine è rilevante''. Ad esempio, le lettere successivamente estratte potrebbero essere ''a,b,c,d'', ma anche ''d,c,b,a''. Le due sequenze rappresentano ''la stessa combinazione'' in quanto differiscono solo nell'ordine ma ''non negli elementi che le costituiscono''. In generale, le quattro lettere ''a,b,c,d'' possono presentarsi in 24 modi diversi da considerarsi però equivalenti ai fini delle combinazioni:

:abcd abdc acbd acdb adbc adcb
:bacd badc bcad bcda bdac bdca
:cabd cadb cbad cbda cdab cdba
:dabc dacb dbac dbca dcab dcba

Non essendo interessati all'ordine di estrazione, dobbiamo dividere 360 per il numero delle sequenze che si possono formare con le stesse 4 lettere, cioè per il numero delle [[Permutazione|permutazioni]] di 4 elementi, dato da 4! = 24. Il risultato finale è:

:<math>C_{6, 4} = \frac{D_{6,4}}{P_4}=\frac {6 \cdot 5 \cdot  4 \cdot  3} {4 \cdot  3 \cdot  2 \cdot  1} = \frac {6 \cdot 5 \cdot  4 \cdot  3} {4!} = \frac {360} {24} = 15.</math>

Generalizzando, se abbiamo ''n'' elementi da raggruppare a ''k'' a ''k'', dobbiamo effettuare il seguente rapporto:

:<math>C_{n, k} = \frac {n (n-1) (n-2) \cdot\cdot\cdot (n-k+1)} {k (k-1) (k-2) \cdot\cdot\cdot 1} = \frac {n (n-1) (n-2) \cdot\cdot\cdot (n-k+1)} {k!}.</math>

Se moltiplichiamo [[numeratore]] e denominatore per ''(n-k)!'' otteniamo, come volevasi dimostrare:

:<math>C_{n, k} = \frac {n (n-1) (n-2) \cdot\cdot\cdot (n-k+1) (n-k)!} {k! (n-k)!} = \frac {n!} {k! (n-k)!}.</math>

Facciamo un ulteriore esempio per ribadire la differenza tra combinazione e disposizione. Se si vuole conoscere il numero di comitati di 3 membri che si possono formare scegliendo tra 6 persone, interessa solo sapere in quanti modi si possono scegliere i membri del comitato indipendentemente da chi venga scelto per primo o per ultimo: in tal caso stiamo considerando le combinazioni e il numero dei comitati possibili è dato da ''C''<sub>6,3</sub> = 20. Se invece volessimo sapere in quanti modi possono presentarsi i primi 3 classificati tra 6 concorrenti, l'ordine sarebbe rilevante: in quest'altro caso stiamo considerando le disposizioni e quindi le possibili classifiche sarebbero date da ''D''<sub>6,3</sub> = 120.

=== Ordine lessicografico ===
Al fine di evitare di considerare erroneamente come valida una combinazione semplice che in realtà è già stata precedentemente presa in considerazione con un altro ordine, si può ricorrere a quest'altra definizione di combinazione.

Si consideri un insieme ''S'' di ''n'' elementi, preventivamente ordinati e si consideri un intero naturale ''k'' tale che 0≤k≤n. Si dice '''combinazione''' di elementi di ''S'' di lunghezza ''k'' ogni sequenza di ''k'' elementi di ''S'' che sia crescente in base all'ordine preventivamente prefissato.

Ad esempio, le combinazioni di lunghezza 4 degli elementi di {''a,b,c,d,e,f''}, preventivamente ordinati secondo il tradizionale ordine alfabetico, sono le seguenti 15:

:abcd abce abcf abde abdf abef acde acdf acef adef
:bcde bcdf bcef bdef
:cdef

Si può notare come le combinazioni rispettino l'[[ordine lessicografico]], in conformità con l'ultima definizione data. Attenendosi all'ordine, si evita di fare confusione considerando come diverse due combinazioni che in realtà non lo sono, tratti in inganno dall'ordine diverso con il quale si presentano i suoi elementi.

=== Criptomorfismo ===
Rifacendoci all'esempio di prima, si possono codificare le combinazioni semplici che abbiamo ottenuto con delle sequenze binarie. Nel nostro caso particolare tali sequenze binarie sono di lunghezza 6 e peso 4 e presentano lo stesso contenuto informativo delle combinazioni indicate nell'esempio. Nella fattispecie, usando numeri binari di 6 cifre, di cui la prima sia 1 se compare la ''a'' e zero in caso contrario, la seconda sia 1 o 0 secondo che compaia o meno la ''b'' ecc., abbiamo:

:111100 111010 111001 110110 110101 110011 101110 101101 101011 100111
:011110 011101 011011 010111
:001111

Si noti come queste sequenze siano presentate in ordine antilessicografico.

In generale, quindi, tra le combinazioni semplici di ''n'' elementi di lunghezza ''k'' e le sequenze binarie di lunghezza ''n'' e peso ''k'' si ha un [[criptomorfismo]] e risulta equivalente operare con le combinazioni o con le sequenze binarie. Poter operare in modo equivalente con le sequenze binarie si rivela molto utile in ambito informatico.

== Combinazioni con ripetizione ==
Nelle combinazioni con ripetizione di lunghezza ''k'', ogni elemento può essere ripetuto fino a ''k'' volte.
Il loro numero è:

:<math>C'_{n,k} = C_{n+k-1,k} = {n + k -1 \choose k} = \frac{(n+k-1)!}{(n-1)!k!}.</math>

Tale risultato può essere dimostrato in diversi modi.

=== Prima dimostrazione ===
Dato un qualsiasi [[insieme finito]] di ''n'' elementi, questo può essere posto in [[corrispondenza biunivoca]] con l'insieme {1, 2, ... , ''n''}.

Per calcolare <math>C'_{n,k}</math> si considerano le sequenze non decrescenti, di lunghezza ''k'', di interi appartenenti a {1, 2, ... , ''n''}. Consideriamo una di queste sequenze:

:<math>m_1,m_2,\dots,m_k</math>

e associamole la sequenza:

:<math>m_1,m_2+1,\dots,m_k+k-1.</math>

La nuova sequenza è strettamente crescente, non presenta ripetizioni e quindi individua una combinazione semplice di lunghezza ''k'' degli interi in {1, 2, ... , ''n''+''k''–1}. La precedente associazione pone in [[corrispondenza biunivoca]] le combinazioni con ripetizioni di lunghezza k degli elementi di {1, 2, ... , ''n''} con le combinazioni semplici di lunghezza ''k'' degli interi in {1, 2, ... , ''n''+''k''-1}. Quindi il numero delle combinazioni con ripetizioni di lunghezza ''k'' dei primi ''n'' interi positivi coincide con il numero delle combinazioni semplici di lunghezza ''k'' dei primi ''n''+''k''-1 interi positivi:

:<math>C'_{n,k} = C_{n+k-1,k} = {n + k -1 \choose k} = \frac{(n+k-1)!}{(n-1)!k!}.</math>

Un esempio può aiutare a comprendere meglio la dimostrazione. Dato l'insieme {1,2}, associamo a ciascuna delle sue combinazioni con ripetizione di classe 3 una sequenza definita come sopra:

:1,1,1 → 1, 1+1, 1+2 → 1,2,3
:1,1,2 → 1, 1+1, 2+2 → 1,2,4
:1,2,2 → 1, 2+1, 2+2 → 1,3,4
:2,2,2 → 2, 2+1, 2+2 → 2,3,4

A ciascuna delle combinazioni con ripetizione corrisponde una ed una sola delle combinazioni semplici di classe 3 dell'insieme {1, ... , (2+3-1)} = {1, 2, 3, 4} e viceversa. Il numero delle prime è quindi uguale al numero delle seconde, che è ''C''<sub>2+3–1,3</sub>.

=== Seconda dimostrazione ===
Il numero delle combinazioni di ''n'' elementi di classe ''k'' è uguale al numero delle [[Funzione monotona|funzioni crescenti]] da un insieme ''A'' di cardinalità ''k'' in un insieme ''B'' di cardinalità ''n''.

Una qualsiasi di tali funzioni è un insieme di [[Coppia (matematica)|coppie]] (''a''<sub>i</sub>,''b''<sub>j</sub>), in cui ''a''<sub>i</sub> è un elemento di ''A'' (con ''i'' = 1,2,...,''k'') e ''b''<sub>j</sub> è un elemento di ''B'' (con ''j'' = 1,2,...,''n''). In tale insieme, vi sono tante coppie quanti sono gli elementi di ''A'' e nessun elemento di ''A'' compare in più di una coppia. Gli elementi di ''B'', inoltre, possono ciascuno comparire in nessuna o più coppie.

Si considerano rilevanti, in una prima fase, le sequenze di coppie; ad esempio, individuate due coppie in cui sia presente al secondo membro un dato elemento ''b'', la sequenza (''a''<sub>1</sub>, ''b''), (''a''<sub>2</sub>, ''b'') è diversa dalla sequenza (''a''<sub>2</sub>, ''b''), (''a''<sub>1</sub>, ''b'').

Si indicano inoltre con ''F''<sub>k</sub> l'insieme delle funzioni da ''A'' in ''B'', con ''F''<sub>k-1</sub> l'insieme delle funzioni da un sottoinsieme di cardinalità ''k''–1 di ''A'' in ''B'', in entrambi i casi considerando distinte, provvisoriamente, funzioni diverse solo per la sequenza delle coppie che condividono il secondo membro.

Sia |''F''<sub>k-1</sub>| il numero delle funzioni dell'ultimo tipo. Vi sono ''n''+''k''–1 modi di estendere ciascuna di tali funzioni a tutto ''A''. Infatti, scelto un qualsiasi elemento ''b''<sub>j</sub> di ''B'', se questo è già presente in altre ''m''<sub>j</sub> coppie (quelle, appunto, il cui secondo membro è ''b''<sub>j</sub>), la nuova coppia (''a''<sub>k</sub>, ''b''<sub>j</sub>) potrà essere posta in sequenza con le altre in ''m''<sub>j</sub>+1 modi diversi: prima della prima, oppure dopo una qualsiasi delle ''m''. Considerando che:

:<math>m_1+m_2+\cdots+m_n=k-1</math>

e che la nuova coppia può avere al secondo membro un qualsiasi elemento di ''B'', si ha:

:<math>(m_1+1)+(m_2+1)+\cdots+(m_n+1)=n+k-1.</math>

La cardinalità dell'insieme ''F''<sub>k</sub> può quindi essere calcolata per [[relazione di ricorrenza|ricorrenza]]:

:<math>\begin{align}|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+k-1)!}{(n-1)!}\end{align}</math>

Si può osservare che si tratta del numero di [[Disposizione|disposizioni semplici]] di (''n''+''k''–1) elementi di classe ''k''.

Per ottenere il numero delle funzioni crescenti, è sufficiente eliminare la distinzione prima introdotta tra funzioni diverse solo per la sequenza delle coppie, quindi scegliere una sola delle ''k''! permutazioni delle coppie (che sono tante quante gli elementi di ''A''). Si ottiene così:

:<math>C'_{n,k}=\frac{(n+k-1)!}{(n-1)!k!}={n+k-1 \choose k}.</math>

Anche qui può essere utile un esempio. Siano ''A'' = {''a''<sub>1</sub>,''a''<sub>2</sub>,''a''<sub>3</sub>} e ''B'' = {''b''<sub>1</sub>,''b''<sub>2</sub>}. L'insieme ''F''<sub>1</sub> contiene solo due funzioni: (''a''<sub>1</sub>,''b''<sub>1</sub>) e (''a''<sub>1</sub>,''b''<sub>2</sub>).

Aggiungiamo ora le coppie che hanno ''a''<sub>2</sub> come primo elemento e consideriamo distinte le funzioni con diverse sequenze delle coppie che condividono il secondo membro. Otteniamo le funzioni in ''F''<sub>2</sub>:

{| border="0" align="center" style="border-top:1px solid black; border-bottom:1px solid black; text-align:center"
|style="border-bottom:1px solid black" | da (''a''<sub>1</sub>,''b''<sub>1</sub>)
|&nbsp;&nbsp;&nbsp;&nbsp;
|style="border-bottom:1px solid black" | da (''a''<sub>1</sub>,''b''<sub>2</sub>)
|-
|(''a''<sub>2</sub>,''b''<sub>1</sub>), (''a''<sub>1</sub>,''b''<sub>1</sub>)
|
|(''a''<sub>2</sub>,''b''<sub>1</sub>), (''a''<sub>1</sub>,''b''<sub>2</sub>)
|-
|(''a''<sub>1</sub>,''b''<sub>1</sub>), (''a''<sub>2</sub>,''b''<sub>1</sub>)
|
|(''a''<sub>2</sub>,''b''<sub>2</sub>), (''a''<sub>1</sub>,''b''<sub>2</sub>)
|-
|(''a''<sub>1</sub>,''b''<sub>1</sub>), (''a''<sub>2</sub>,''b''<sub>2</sub>)
|
|(''a''<sub>1</sub>,''b''<sub>2</sub>), (''a''<sub>2</sub>,''b''<sub>2</sub>)
|}

Si ha quindi:

:<math>\begin{align}F_1 &= n = 2,\\F_2 &= (n+1)F_1= (2+1)\cdot2 = 6.\end{align}</math>

Si tratta delle 6 disposizioni semplici di (2+2-1) = 3 elementi di classe 2. I tre elementi sono i due elementi di ''A'' finora considerati ed un "elemento di separazione" che consenta di distinguere quali sono associati a ''b''<sub>1</sub> e quali a ''b''<sub>2</sub>. Indicando tale elemento con una [[barra verticale]], le sei funzioni sono:

# ''a''<sub>1</sub> ''a''<sub>2</sub> | &nbsp;&nbsp;&nbsp;&nbsp;(entrambi associati a ''b''<sub>1</sub>)
# ''a''<sub>2</sub> ''a''<sub>1</sub> | &nbsp;&nbsp;&nbsp;&nbsp;(entrambi associati a ''b''<sub>1</sub>)
# ''a''<sub>1</sub> | ''a''<sub>2</sub> &nbsp;&nbsp;&nbsp;&nbsp;(''a''<sub>1</sub> associato a ''b''<sub>1</sub>, ''a''<sub>2</sub> associato a ''b''<sub>2</sub>)
# ''a''<sub>2</sub> | ''a''<sub>1</sub> &nbsp;&nbsp;&nbsp;&nbsp;(''a''<sub>2</sub> associato a ''b''<sub>1</sub>, ''a''<sub>1</sub> associato a ''b''<sub>2</sub>)
# | ''a''<sub>1</sub> ''a''<sub>2</sub> &nbsp;&nbsp;&nbsp;&nbsp;(entrambi associati a ''b''<sub>2</sub>)
# | ''a''<sub>2</sub> ''a''<sub>1</sub> &nbsp;&nbsp;&nbsp;&nbsp;(entrambi associati a ''b''<sub>2</sub>)

Per ottenere il numero delle funzioni crescenti, quelle cioè tali che se ''i'' &lt; ''j'' allora ''f''(''a''<sub>i</sub>) ≤ ''f''(''a''<sub>j</sub>), basta dividere per il numero delle permutazioni dei due elementi di ''A'', che sono 2! = 2. Si ottiene così che le funzioni crescenti sono 6/2 = 3 (sono quelle al primo, terzo e quinto posto dell'elenco).

Per estendere le funzioni a tutto ''A'', aggiungiamo le coppie che hanno ''a''<sub>3</sub> come primo elemento:

{| border="0" align="center" style="border-top:1px solid black; border-bottom:1px solid black; text-align:center"
|style="border-bottom:1px solid black" | da (''a''<sub>2</sub>,''b''<sub>1</sub>), (''a''<sub>1</sub>,''b''<sub>1</sub>)
|
|style="border-bottom:1px solid black" | da (''a''<sub>1</sub>,''b''<sub>1</sub>), (''a''<sub>2</sub>,''b''<sub>1</sub>)
|
|style="border-bottom:1px solid black" | da (''a''<sub>1</sub>,''b''<sub>1</sub>), (''a''<sub>2</sub>,''b''<sub>2</sub>)
|
|style="border-bottom:1px solid black" | da (''a''<sub>2</sub>,''b''<sub>1</sub>), (''a''<sub>1</sub>,''b''<sub>2</sub>)
|
|style="border-bottom:1px solid black" | da (''a''<sub>2</sub>,''b''<sub>2</sub>), (''a''<sub>1</sub>,''b''<sub>2</sub>)
|
|style="border-bottom:1px solid black" | da (''a''<sub>1</sub>,''b''<sub>2</sub>), (''a''<sub>2</sub>,''b''<sub>2</sub>)
|-
| (''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>1</sub>)
|
| (''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>1</sub>)
|
| (''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>)
|-
| (''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>1</sub>)
|
| (''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>1</sub>)
|
| (''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>3</sub>,''b''<sub>2</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>3</sub>,''b''<sub>2</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>)
|-
| (''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>1</sub>)
|
| (''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>1</sub>)
|
| (''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>2</sub>,''b''<sub>2</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>1</sub>,''b''<sub>2</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>)
|-
| (''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>2</sub>,''b''<sub>2</sub>),(''a''<sub>1</sub>,''b''<sub>2</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>)
|
| (''a''<sub>1</sub>,''b''<sub>2</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>)
|}

per un totale di 24 coppie. Si ha quindi:

:<math>F_3 = (n+k-1)F_2 = (2+3-1)\cdot 6= 24.</math>

Questo è il numero delle disposizioni semplici di (2+3-1) = 4 elementi di classe 3, dove i quattro elementi sono ''a''<sub>1</sub>, ''a''<sub>2</sub>, ''a''<sub>3</sub> e l'"elemento separatore" che consente di distinguere se sono associati a ''b''<sub>1</sub> oppure a ''b''<sub>2</sub>. Il numero delle funzioni crescenti si ottiene dividendo per il numero delle permutazioni dei tre elementi di ''A'': 24/3! = 24/6 = 4. Le funzioni crescenti sono, infatti:
# ''a''<sub>1</sub> ''a''<sub>2</sub> ''a''<sub>3</sub> | &nbsp;&nbsp; ovvero &nbsp;&nbsp; (''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>1</sub>)
# ''a''<sub>1</sub> ''a''<sub>2</sub> | ''a''<sub>3</sub> &nbsp;&nbsp; ovvero &nbsp;&nbsp; (''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>1</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>)
# ''a''<sub>1</sub> | ''a''<sub>2</sub> ''a''<sub>3</sub> &nbsp;&nbsp; ovvero &nbsp;&nbsp; (''a''<sub>1</sub>,''b''<sub>1</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>)
# | ''a''<sub>1</sub> ''a''<sub>2</sub> ''a''<sub>3</sub> &nbsp;&nbsp; ovvero &nbsp;&nbsp; (''a''<sub>1</sub>,''b''<sub>2</sub>),(''a''<sub>2</sub>,''b''<sub>2</sub>),(''a''<sub>3</sub>,''b''<sub>2</sub>)

=== Terza dimostrazione ===
La precedente dimostrazione può essere semplificata come segue. Dato un insieme ''A'' di ''k'' elementi, vogliamo ripartire i suoi elementi in ''n'' gruppi, ciascuno contenente da 0 a ''k'' volte un elemento di ''A''. Rappresentiamo gli elementi di ''A'' con asterischi, i gruppi con ''n''–1 barre verticali; ad esempio, se ''n'' = 4 e ''k'' = 6, possiamo avere ripartizioni come le seguenti (tra parentesi il numero di elementi in ciascun gruppo):

: ∗ ∗ | ∗ ∗ | ∗ | ∗ &nbsp;&nbsp;&nbsp;&nbsp; (2,2,1,1)
: |  ∗ ∗ ∗ | ∗ | ∗ ∗ &nbsp;&nbsp;&nbsp;&nbsp; (0,3,1,2)

oppure:

: ∗ ∗ | | | ∗ ∗ ∗ ∗ &nbsp;&nbsp;&nbsp;&nbsp; (2,0,0,4)

o anche:

: ∗ ∗ ∗ ∗ ∗ ∗ | | | &nbsp;&nbsp;&nbsp;&nbsp; (6,0,0,0)

I gruppi racchiudono gli elementi ripetuti, se sostituissimo gli asterischi con delle lettere {a,b,c,d,e,f} otterremmo nel primo esempio: aa|bb|c|d. Li rappresentiamo come asterischi perché essendo combinazioni il loro valore non è influente. L'insime di asterischi e barre rappresente l'insieme di tutte le combinazioni degli elementi con le loro possibili ripetizioni.

In ciascuna rappresentazione abbiamo una sequenza di ''n''+''k''–1 simboli. Dal momento che non interessa l'ordine, si tratta solo di vedere in quanti modi si possono scegliere ''n''–1 di tali simboli per farne delle barre. In altre parole, si tratta di trovare tutte le possibili [[permutazione|permutazioni]] di ''n''+''k''–1 simboli, considerando che ''k'' sono uguali tra loro (gli asterischi) e lo stesso vale per le ''n''–1 barre verticali. Si ha quindi, per una proprietà del [[coefficiente binomiale]] e tenendo conto della formula per [[permutazione#Insiemi con ripetizioni|permutazioni con ripetizioni]]:

:<math>C'_{n,k}={n+k-1 \choose n-1}={n+k-1 \choose (n+k-1)-(n-1)}={n+k-1 \choose k}.</math>

=== Esempi ===
Le combinazioni con ripetizione di lunghezza 2 dei primi 5 interi positivi sono:

:<math>C'_{5,2}={5+2-1 \choose 2} = \frac{6!}{4!2!} = 15</math>

e precisamente: 11, 12, 13, 14, 15, 22, 23, 24, 25, 33, 34, 35, 44, 45, 55.

Si può però anche avere ''k'' &gt; ''n'': ad esempio, le combinazioni di lunghezza 5 dei primi 2 interi positivi sono:

:<math>C'_{2,5}={2+5-1 \choose 5} = \frac{6!}{1!5!} = 6</math>

ossia: 11111, 11112, 11122, 11222, 12222, 22222.

=== Numero di soluzioni intere di un'equazione ===
Il calcolo delle combinazioni con ripetizione consente di trovare il numero delle soluzioni intere non negative di un'equazione in ''n'' variabili del tipo:

:<math>x_1+x_2+\cdots+x_n=k.</math>

In questo caso ''k'' può essere visto come il numero delle unità che si possono ripartire in ''n'' gruppi diversi, anche vuoti, quindi come il numero degli asterischi della terza dimostrazione, svolgendo i "+" il ruolo delle barre. Ad esempio, l'equazione:

:<math>x_1+x_2+x_3+x_4 = 6</math>

ammette, tra le altre, le seguenti soluzioni (tra parentesi la rappresentazioni con sequenze di "1" e "+"):

:<math>x_1=2, x_2=2, x_3=1, x_4=1\qquad(11+11+1+1)</math>
:<math>x_1=0, x_2=3, x_3=1, x_4=2\qquad(+111+1+11)</math>
:<math>x_1=2, x_2=0, x_3=0, x_4=4\qquad(11+++1111)</math>
:<math>x_1=6, x_2=0, x_3=0, x_4=0\qquad(111111+++)</math>

Trovare il loro numero equivale a trovare il numero delle combinazioni con ripetizione di ''n'' elementi di classe ''k''. Nel caso dell'equazione data, il numero è:

:<math>C'_{4,6}={4+6-1 \choose 4-1}={4+6-1 \choose 6}=84.</math>

Per un caso più semplice, le soluzioni intere non negative dell'equazione

:<math>x_1+x_2=3</math>

sono:

:<math>C'_{2,3}={2+3-1 \choose 2-1}={2+3-1 \choose 3}=4</math>

ossia le quattro coppie (0,3), (1,2), (2,1), (3,0).

Si può anche calcolare il numero delle soluzioni intere positive di un'equazione (detto "numero delle composizioni di ''k'' in ''n'' parti"). Data un'equazione del tipo:

:<math>x_1+x_2+\cdots+x_n=k</math>

basta trasformarla in:

:<math>y_1+y_2+\cdots+y_n=k-n</math>

ponendo ''y''<sub>i</sub> = ''x''<sub>i</sub>–1. Si ottiene così:

:<math>{n+(k-n)-1 \choose n-1}={k-1 \choose n-1}.</math>

Nel caso dell'equazione ''x''<sub>1</sub>+''x''<sub>2</sub> = 3, il numero delle soluzioni intere positive (il numero delle composizioni di 3 in 2 parti) è:

:<math>{3-1 \choose 2-1}={2 \choose 1}=2</math>

ossia le due coppie (1,2) e (2,1).

=== Multiinsiemi ===
Il numero delle combinazioni con ripetizione di ''n'' elementi di classe ''k'' è il numero dei [[Multiinsieme|multiinsiemi]] di cardinalità ''k'' con sostegno un insieme di cardinalità ''n''.

Si usa, al riguardo, la definizione di multiinsieme come funzione ''m''<sub>U</sub>: ''U'' → {0,1,2,...}. Ad esempio, dato l'insieme ''U'' = {''a'',''b'',''c''}, un multiinsieme di cardinalità 3 è {(''a'',0), (''b'',2), (''c'',1)}, ossia, nella notazione esponenziale, ''a''<sup>0</sup> ''b''<sup>2</sup> ''c''<sup>1</sup>. La sua cardinalità è la somma dei secondi membri delle coppie, o degli esponenti nella seconda notazione. Tale multiinsieme può essere rappresentato come una delle possibili combinazioni con ripetizione di classe 3 dei 3 elementi di ''U'': ''bbc''.

Il numero delle combinazioni con ripetizione di classe 3 dei 3 elementi di ''U'' è (3+3–1)!/(2!3!) = 10; le combinazioni sono:

:''aaa, aab, aac, abb, abc, acc, bbb, bbc, bcc, ccc.''

Questo è anche il numero dei multiinsiemi di cardinalità 3 di ''U'', che sono:

:''a''<sup>3</sup>''b''<sup>0</sup>''c''<sup>0</sup>, ''a''<sup>2</sup>''b''<sup>1</sup>''c''<sup>0</sup>, ''a''<sup>2</sup>''b''<sup>0</sup>''c''<sup>1</sup>, ''a''<sup>1</sup>''b''<sup>2</sup>''c''<sup>0</sup>, ''a''<sup>1</sup>''b''<sup>1</sup>''c''<sup>1</sup>, ''a''<sup>1</sup>''b''<sup>0</sup>''c''<sup>2</sup>, ''a''<sup>0</sup>''b''<sup>3</sup>''c''<sup>0</sup>, ''a''<sup>0</sup>''b''<sup>2</sup>''c''<sup>1</sup>, ''a''<sup>0</sup>''b''<sup>1</sup>''c''<sup>2</sup>, ''a''<sup>0</sup>''b''<sup>0</sup>''c''<sup>3</sup>

Si può notare che il loro numero è anche uguale a quello delle soluzioni intere non negative dell'equazione:

:<math>x_1+x_2+x_3=3.</math>
==Note==
<references/>
== Bibliografia ==
* [[Mauro Cerasoli]], [[Franco Eugeni]] e [[Marco Protasi]], ''Elementi di matematica discreta'', Zanichelli, Bologna, 1988.
* Sheldon M. Ross, ''Calcolo delle probabilità'', Apogeo, Milano, 2004.

== Voci correlate ==
* [[Calcolo combinatorio]]
* [[Disposizione]]
* [[Multinsieme]]
* [[Permutazione]]
* [[Reticolo booleano]]
* [[Triangolo di Tartaglia]]

== Altri progetti ==
{{interprogetto|preposizione=sulla|wikt=combinazione|wikt_etichetta=combinazione}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{cita web|url=https://www.youtube.com/watch?v=8x-RHlV0ysQ|titolo=Un'applicazione pratica delle combinazioni semplici}}
* [http://www.lucamoroni.it/lancio-dadi-con-una-data-somma/ Se lancio più dadi, qual è la probabilità di ottenere una certa somma?] Un'applicazione delle combinazioni con ripetizione al lancio di più dadi

{{Algebra}}
{{Combinatoria}}
{{Controllo di autorità}}
{{Portale|matematica}}

[[Categoria:Combinatoria]]