Combinazione

Nel calcolo combinatorio, dati ${\displaystyle n}$ e ${\displaystyle k}$ due interi non negativi, si definisce combinazione di un insieme di ${\displaystyle n}$ elementi presi ${\displaystyle k}$ alla volta (oppure di classe ${\displaystyle k}$, o a ${\displaystyle k}$ a ${\displaystyle k}$) ogni multiinsieme di ${\displaystyle k}$ elementi che appartengono all'insieme (detti anche "estratti" dall'insieme) di quegli ${\displaystyle n}$ elementi. Una combinazione è detta semplice, o senza ripetizioni, se e solo se ogni suo membro ha molteplicità 1 (ossia non ci sono elementi che si ripetono), e combinazione con ripetizione altrimenti. Una combinazione semplice di ${\displaystyle n}$ elementi di classe ${\displaystyle k}$ è perciò equivalente a un sottoinsieme, di cardinalità ${\displaystyle k}$, dell'insieme degli ${\displaystyle n}$ elementi dai quali è estratta, dunque in tal caso ${\displaystyle k\leq n}$. A volte, per questi motivi, se si vuole specificare che una combinazione di ${\displaystyle n}$ elementi di classe ${\displaystyle k}$ è una combinazione semplice, viene direttamente chiamata un ${\displaystyle k}$-insieme di (un insieme di) ${\displaystyle n}$ elementi; invece una combinazione con ripetizioni è chiamata un ${\displaystyle k}$-multiinsieme di (un insieme di) ${\displaystyle n}$ elementi.^[1]

Disambiguazione – Se stai cercando altri significati, vedi Combinazione (disambigua).

Sottoinsiemi da 3 elementi di un insieme di 5 elementi

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 (disposizioni di n elementi di classe k) per il numero delle permutazioni di k elementi:

${\displaystyle C_{n,k}={\frac {D_{n,k}}{P_{k}}}={\frac {\frac {n!}{(n-k)!}}{k!}}={\frac {n!}{(n-k)!k!}}={n \choose k}.}$

Il simbolo ${\displaystyle {n \choose k}}$ viene detto coefficiente binomiale.

Giustificazione della formula

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

${\displaystyle C_{6,4}={\frac {6!}{(6-4)!4!}}={\frac {6!}{2!4!}}={\frac {720}{2\cdot 24}}=15.}$

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 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 permutazioni di 4 elementi, dato da 4! = 24. Il risultato finale è:

${\displaystyle 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.}$

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

${\displaystyle 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!}}.}$

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

${\displaystyle 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)!}}.}$

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_6,3 = 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_6,3 = 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 è:

${\displaystyle C'_{n,k}=C_{n+k-1,k}={n+k-1 \choose k}={\frac {(n+k-1)!}{(n-1)!k!}}.}$

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 ${\displaystyle C'_{n,k}}$ si considerano le sequenze non decrescenti, di lunghezza k, di interi appartenenti a {1, 2, ... , n}. Consideriamo una di queste sequenze:

${\displaystyle m_{1},m_{2},\dots ,m_{k}}$

e associamole la sequenza:

${\displaystyle m_{1},m_{2}+1,\dots ,m_{k}+k-1.}$

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:

${\displaystyle C'_{n,k}=C_{n+k-1,k}={n+k-1 \choose k}={\frac {(n+k-1)!}{(n-1)!k!}}.}$

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_2+3–1,3.

Seconda dimostrazione

Il numero delle combinazioni di n elementi di classe k è uguale al numero delle funzioni crescenti da un insieme A di cardinalità k in un insieme B di cardinalità n.

Una qualsiasi di tali funzioni è un insieme di coppie (a_i,b_j), in cui a_i è un elemento di A (con i = 1,2,...,k) e b_j è 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₁, b), (a₂, b) è diversa dalla sequenza (a₂, b), (a₁, b).

Si indicano inoltre con F_k l'insieme delle funzioni da A in B, con F_k-1 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_k-1| 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_j di B, se questo è già presente in altre m_j coppie (quelle, appunto, il cui secondo membro è b_j), la nuova coppia (a_k, b_j) potrà essere posta in sequenza con le altre in m_j+1 modi diversi: prima della prima, oppure dopo una qualsiasi delle m. Considerando che:

${\displaystyle m_{1}+m_{2}+\cdots +m_{n}=k-1}$

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

${\displaystyle (m_{1}+1)+(m_{2}+1)+\cdots +(m_{n}+1)=n+k-1.}$

La cardinalità dell'insieme F_k può quindi essere calcolata per ricorrenza:

${\displaystyle {\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+k-1)!}{(n-1)!}}\end{aligned}}}$

Si può osservare che si tratta del numero di 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ì:

${\displaystyle C'_{n,k}={\frac {(n+k-1)!}{(n-1)!k!}}={n+k-1 \choose k}.}$

Anche qui può essere utile un esempio. Siano A = {a₁,a₂,a₃} e B = {b₁,b₂}. L'insieme F₁ contiene solo due funzioni: (a₁,b₁) e (a₁,b₂).

Aggiungiamo ora le coppie che hanno a₂ come primo elemento e consideriamo distinte le funzioni con diverse sequenze delle coppie che condividono il secondo membro. Otteniamo le funzioni in F₂:

da (a1,b1)		da (a1,b2)
(a2,b1), (a1,b1)		(a2,b1), (a1,b2)
(a1,b1), (a2,b1)		(a2,b2), (a1,b2)
(a1,b1), (a2,b2)		(a1,b2), (a2,b2)

Si ha quindi:

${\displaystyle {\begin{aligned}F_{1}&=n=2,\\F_{2}&=(n+1)F_{1}=(2+1)\cdot 2=6.\end{aligned}}}$

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₁ e quali a b₂. Indicando tale elemento con una barra verticale, le sei funzioni sono:

1. a₁ a₂ |     (entrambi associati a b₁)
2. a₂ a₁ |     (entrambi associati a b₁)
3. a₁ | a₂     (a₁ associato a b₁, a₂ associato a b₂)
4. a₂ | a₁     (a₂ associato a b₁, a₁ associato a b₂)
5. | a₁ a₂     (entrambi associati a b₂)
6. | a₂ a₁     (entrambi associati a b₂)

Per ottenere il numero delle funzioni crescenti, quelle cioè tali che se i < j allora f(a_i) ≤ f(a_j), 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₃ come primo elemento:

da (a2,b1), (a1,b1)		da (a1,b1), (a2,b1)		da (a1,b1), (a2,b2)		da (a2,b1), (a1,b2)		da (a2,b2), (a1,b2)		da (a1,b2), (a2,b2)
(a3,b1),(a2,b1),(a1,b1)		(a3,b1),(a1,b1),(a2,b1)		(a3,b1),(a1,b1),(a2,b2)		(a3,b1),(a2,b1),(a1,b2)		(a3,b1),(a2,b2),(a1,b2)		(a3,b1),(a1,b2),(a2,b2)
(a2,b1),(a3,b1),(a1,b1)		(a1,b1),(a3,b1),(a2,b1)		(a1,b1),(a3,b1),(a2,b2)		(a2,b1),(a3,b1),(a1,b2)		(a3,b2),(a2,b2),(a1,b2)		(a3,b2),(a1,b2),(a2,b2)
(a2,b1),(a1,b1),(a3,b1)		(a1,b1),(a2,b1),(a3,b1)		(a1,b1),(a3,b2),(a2,b2)		(a2,b1),(a3,b2),(a1,b2)		(a2,b2),(a3,b2),(a1,b2)		(a1,b2),(a3,b2),(a2,b2)
(a2,b1),(a1,b1),(a3,b2)		(a1,b1),(a2,b1),(a3,b2)		(a1,b1),(a2,b2),(a3,b2)		(a2,b1),(a1,b2),(a3,b2)		(a2,b2),(a1,b2),(a3,b2)		(a1,b2),(a2,b2),(a3,b2)

per un totale di 24 coppie. Si ha quindi:

${\displaystyle F_{3}=(n+k-1)F_{2}=(2+3-1)\cdot 6=24.}$

Questo è il numero delle disposizioni semplici di (2+3-1) = 4 elementi di classe 3, dove i quattro elementi sono a₁, a₂, a₃ e l'"elemento separatore" che consente di distinguere se sono associati a b₁ oppure a b₂. 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:

1. a₁ a₂ a₃ |    ovvero    (a₁,b₁),(a₂,b₁),(a₃,b₁)
2. a₁ a₂ | a₃    ovvero    (a₁,b₁),(a₂,b₁),(a₃,b₂)
3. a₁ | a₂ a₃    ovvero    (a₁,b₁),(a₂,b₂),(a₃,b₂)
4. | a₁ a₂ a₃    ovvero    (a₁,b₂),(a₂,b₂),(a₃,b₂)

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):

∗ ∗ | ∗ ∗ | ∗ | ∗      (2,2,1,1)

| ∗ ∗ ∗ | ∗ | ∗ ∗      (0,3,1,2)

oppure:

∗ ∗ | | | ∗ ∗ ∗ ∗      (2,0,0,4)

o anche:

∗ ∗ ∗ ∗ ∗ ∗ | | |      (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 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 permutazioni con ripetizioni:

${\displaystyle C'_{n,k}={n+k-1 \choose n-1}={n+k-1 \choose (n+k-1)-(n-1)}={n+k-1 \choose k}.}$

Esempi

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

${\displaystyle C'_{5,2}={5+2-1 \choose 2}={\frac {6!}{4!2!}}=15}$

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

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

${\displaystyle C'_{2,5}={2+5-1 \choose 5}={\frac {6!}{1!5!}}=6}$

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:

${\displaystyle x_{1}+x_{2}+\cdots +x_{n}=k.}$

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:

${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=6}$

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

${\displaystyle x_{1}=2,x_{2}=2,x_{3}=1,x_{4}=1\qquad (11+11+1+1)}$

${\displaystyle x_{1}=0,x_{2}=3,x_{3}=1,x_{4}=2\qquad (+111+1+11)}$

${\displaystyle x_{1}=2,x_{2}=0,x_{3}=0,x_{4}=4\qquad (11+++1111)}$

${\displaystyle x_{1}=6,x_{2}=0,x_{3}=0,x_{4}=0\qquad (111111+++)}$

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 è:

${\displaystyle C'_{4,6}={4+6-1 \choose 4-1}={4+6-1 \choose 6}=84.}$

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

${\displaystyle x_{1}+x_{2}=3}$

sono:

${\displaystyle C'_{2,3}={2+3-1 \choose 2-1}={2+3-1 \choose 3}=4}$

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:

${\displaystyle x_{1}+x_{2}+\cdots +x_{n}=k}$

basta trasformarla in:

${\displaystyle y_{1}+y_{2}+\cdots +y_{n}=k-n}$

ponendo y_i = x_i–1. Si ottiene così:

${\displaystyle {n+(k-n)-1 \choose n-1}={k-1 \choose n-1}.}$

Nel caso dell'equazione x₁+x₂ = 3, il numero delle soluzioni intere positive (il numero delle composizioni di 3 in 2 parti) è:

${\displaystyle {3-1 \choose 2-1}={2 \choose 1}=2}$

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 multiinsiemi di cardinalità k con sostegno un insieme di cardinalità n.

Si usa, al riguardo, la definizione di multiinsieme come funzione m_U: 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⁰ b² c¹. 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³b⁰c⁰, a²b¹c⁰, a²b⁰c¹, a¹b²c⁰, a¹b¹c¹, a¹b⁰c², a⁰b³c⁰, a⁰b²c¹, a⁰b¹c², a⁰b⁰c³

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

${\displaystyle x_{1}+x_{2}+x_{3}=3.}$

Note

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

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

Altri progetti

• Wikizionario
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «combinazione»
• Wikimedia Commons contiene immagini o altri file sulla combinazione

Collegamenti esterni

• Combinazione, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• Combinazione, in Dizionario delle scienze fisiche, Istituto dell'Enciclopedia Italiana, 1996.
• Combinazióne, su Vocabolario Treccani, Istituto dell'Enciclopedia Italiana.
• combinazióne, su sapere.it, De Agostini.
• Combinazione, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) combination, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Opere riguardanti Combinations, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Combination, su MathWorld, Wolfram Research.
• (EN) Combination, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• Un'applicazione pratica delle combinazioni semplici, su youtube.com.
• Se lancio più dadi, qual è la probabilità di ottenere una certa somma? Un'applicazione delle combinazioni con ripetizione al lancio di più dadi

Controllo di autorità	Thesaurus BNCF 32733

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica