Combinazioni – ValCon.It

Dati n oggetti tutti diversi (a, b, c, …) la scrittura C_n,k significa

In quanti modi si possono scegliere k oggetti, considerando uguali due sequenze con gli stessi oggetti
Quante squadre di k elementi si possono comporre avendo a disposizione n persone
Quante combinazioni semplici di n elementi di classe k

Prova…

n	k = 0	k = 1	k = 2	k = 3	k = 4	k = 5
0	{}
1	{}	`A`
2	{}	`A B`	`AB`
3	{}	`A B C`	`AB AC BC`	`ABC`
4	{}	`A B C D`	`AB AC AD BC BD CD`	`ABC ABD ACD BCD`	`ABCD`
5	{}	`A B C D E`	AB AC AD AE BC BD BE CD CE DE	`ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE`	`ABCD ABCE ABDE ACDE BCDE`	`ABCDE`
6	{}	`A B C D E F`	`AB AC AD AE AF BC BD BE BF CD CE CF DE DF EF`	`ABC ABD ABE ABF ACD ACE ACF ADE ADF BCD BCE BCF BDE BDF BEF CDE CDF CEF DEF`	`ABCD ... CDEF`	`ABCDE ... BCDEF`
7	{}	`A B C D E F G`	`AB AC AD AE AF AG BC BD BE BF BG CD CE CF CG DE DF DG EF EG FG`	`ABC ... EFG`	`ABCD ... DEFG`	`ABCDE ... CDEFG`
8	{}	`...`	`AB ... GH`	`ABC ... FGH`	`ABCD ... EFGH`	`ABCDE ... DEFGH`

Ecco i conti della tabella precedente

+---+----------------------------+ | | 0 1 2 3 4 5 6 7 8 | +---+----------------------------+ | 0 | 1 | | 1 | 1 1 | | 2 | 1 2 1 | | 3 | 1 3 3 1 | | 4 | 1 4 6 4 1 | | 5 | 1 5 10 10 5 1 | | 6 | 1 6 15 20 15 6 1 | | 7 | 1 7 21 35 35 21 7 1 | | 8 | 1 8 28 56 70 56 28 8 1 | +---+----------------------------+

Osserva

Scelgo il 1° simbolo tra n
Scelgo il 2° simbolo tra n-1 rimanenti
…
Scelgo il k° simbolo tra n-k+1 rimanenti

Si ottengono $n(n-1)(n-2)\dots (n-k+1)$ sequenze ma non sono tutte diverse…

Ci sono $k(k-1)(k-2)\dots 1$ sequenze per ogni scelta di k simboli diversi, quindi i valori di $\displaystyle {n \choose k}$ , coefficiente binomiale n sopra k, sono

$C_{n,k}$ = $\displaystyle {n \choose k}$ = $\displaystyle \frac{n(n-1)(n-2)\dots (n-k+1)}{k!}$ = $\displaystyle \frac{n!}{k!(n-k)!}$

Proprietà 1

Dall’osservazione della tabella risulta

$\displaystyle {n \choose 0} = {n \choose n} = 1$

$\displaystyle {n \choose 1} = {n \choose n-1} = n$

In generale

$\displaystyle {n \choose k} = {n \choose n-k}$

Proprietà 2

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

Osserva

2 = 1+1
10 = 6+4 = 4+6
8 = 7+1 = 1+7
70 = 35+35
…

Proprietà 3

$\displaystyle {n \choose k+1} = {n \choose k}\cdot \frac{n-k}{k+1}$

Esempi

$\displaystyle {5 \choose 2} = {5 \choose 1}\cdot \frac{4}{2}$ = $\displaystyle 5 \cdot 2$ = 10
$\displaystyle {8 \choose 4} = {8 \choose 3}\cdot \frac{5}{4}$ = $\displaystyle 56 \cdot \frac{5}{4}$ = 70
…

Triangolo di Tartaglia

Le proprietà 1 e 2 della tabella sono più evidenti se si cambia la disposizione dei valori

+---+---------------------------------------------------+ | 0 | 1 | | 1 | 1 1 | | 2 | 1 2 1 | | 3 | 1 3 3 1 | | 4 | 1 4 6 4 1 | | 5 | 1 5 10 10 5 1 | | 6 | 1 6 15 20 15 6 1 | | 7 | 1 7 21 35 35 21 7 1 | | 8 | 1 8 28 56 70 56 28 8 1 | +---+---------------------------------------------------+