Webtudordimatematica

Le combinazioni nel calcolo combinatorio

Nel calcolo combinatorio le combinazioni si usano quando è necessario contare in quanti modi possiamo sistemare $n$ oggetti in $k$ posti a prescindere dall'ordine in cui sistemiamo gli oggetti. Ad esempio, se vuoi sapere in quanti modi possibili puoi far sedere n=17 persone su k=3 sedie disponibili, devi calcolare le combinazioni di 17 oggetti (le persone) a 3 a 3 (i posti). In questo modo i raggruppamenti che si vanno a formare cambiano soltanto in base a quali oggetti includiamo tra gli $n$ e non per l'ordine in cui vengono disposti. Infatti, nell'esempio precedente non importa in quale ordine fai sedere le persone ma QUALI PERSONE fai sedere ("qualità").

Pertanto, due qualunque combinazioni della stessa classe $k$ differiscono per almeno un elemento ("qualità"). Come mostrato qui sotto, una combinazione potrebbe essere formata da Letizia, Marika e Samuel, mentre un'altra potrebbe avere Filippo al posto di Marika e quindi differenziarsi per la presenza di una persona diversa.

 combinazione semplice 1                                                       combinazione semplice 2

A seconda che gli oggetti si ripetano o meno, si distinguono due tipi di combinazioni.

  1. Combinazioni semplici (gli oggetti sono tutti distinti nei raggruppamenti)
  2. Combinazioni con ripetizione (alcuni degli oggetti si possono ripetere nei raggruppamenti)

Combinazioni semplici

Si dicono combinazioni semplici di $n$ elementi a $k$ a $k$ (o di classe $k$), $C_{n,k}$, tutti i raggruppamenti non ordinati formati con $k$ elementi distinti presi dagli $n$.

$$\bbox[#ffffff,5px,border:2px solid #ff6600]{C_{n,k}=\frac{n\cdot (n-1)\cdot (n-2)\dots (n-k+1)}{k!}}$$

L'esempio fatto sopra con le persone è un esempio di combinazioni semplici

Esempio combinazioni semplici

Sia $A=\{a_1,a_2,a_3\}$, si ha $n=3$ e $1\le k\le n=3$, ovvero, k può essere 1,2 oppure 3.

  1. Per k=1 le combinazioni semplici di A di classe 1 sono $C_{3,1}=\frac{3\cdot 1}{1!}=3$:
  2. $$a_1,\ a_2,\ a_3$$
  3. Per k=2 le combinazioni semplici di A di classe 2 sono $C_{3,2}=\frac{3\cdot 2}{2!}=3$:
  4. $$(a_1,a_2)\ (a_1,a_3)\ (a_2,a_3)$$
  5. Per k=3 le combinazioni semplici di A di classe 2 sono $C_{3,3}=\frac{3\cdot 2\cdot 1}{3!}=1$:
  6. $$(a_1,a_2,a_3)$$

Proprietà delle combinazioni semplici

Osserviamo che da una qualsiasi combinazione di classe k di A si ottengono $k!$ disposizioni contenenti i medesimi elementi della combinazione considerata, per cui $C_{n,k}\cdot k!=D_{n,k}$ ossia:

$$\bbox[#ffffff,5px,border:2px solid #ff6600]{C_{n,k}=\frac{D_{n,k}}{k!}\frac{n\cdot (n-1)\cdot (n-2)\dots (n-k+1)}{k!}}$$

 

Coefficiente binomiale

Dati $n,k\in\mathbb N$ con $k\le n$, chiamasi coefficiente binomiale di n su k il simbolo ${n \choose k}$ e si ha:

$$\bbox[#ffffff,5px,border:2px solid #ff6600]{{n \choose k}=\frac{n!}{k!(n-k)!}\left(=C_{n,k}\right)}$$

Proprietà del coefficiente binomiale

Il coefficiente binomiale gode di alcune proprietà che semplificano notevolmente i calcoli in certe situazioni. Te le presento qui di seguito

  • ${n\choose 0}=1$
  • ${n\choose 1}=n$
  • ${n\choose n}=1$
  • Simmetria dei coefficienti binomiali: $\quad{n\choose k}={n\choose n-k}$
  • Formula di Stifel: $\quad{n\choose k}={n-1\choose k-1}+{n-1\choose k}$

Guarda il video che ho registrato in cui ti spiego come calcolare il coefficiente binomiale.

 

 

Combinazioni con ripetizione

Quando uno stesso elemento tra gli $n$ da disporre nei $k$ posti compare più di una volta nei raggruppamenti, si parla di combinazioni con ripetizione. Ad esempio, supponi di voler sapere in quanti modi puoi collocare 10 palline di cui 3 gialle, 2 rosse, 4 blu e 1 verde in 4 buche (una per buca). Dato che le palline dello stesso colore sono indistinguibili (si ripetono) si possono formare raggruppamenti in cui la pallina gialla compare 1, 2 o 3 volte oppure quella blu compare fino a 4 volte, ecc.

Si dicono combinazioni con ripetizione degli n elementi di A presi a k a k (o di classe k), $C_{n,k}^r$, tutti i raggruppamenti non ordinati formati con k elementi, in cui ogni elemento può ripetersi fino a k volte.

$$\bbox[#ffffff,5px,border:2px solid #ff6600]{C_{n,k}^r=\frac{n\cdot (n+1)\cdot \dots \cdot (n+k-1)}{k!}}$$

Pertanto, due qualunque combinazioni con ripetizione di classe $k$ differiscono o perché contengono elementi diversi ("qualità") o per il numero di volte in cui un elemento è ripetuto.

Esempio combinazioni con ripetizione

Sia $A=\{a,b,c\}$, si ha $n=3$.

  1. Per k=1 le combinazioni con ripetizione di A di classe 1 sono $C_{3,1}^r=3$
  2. $$(a)\ (b)\ (c)$$
  3. Per k=2 le combinazioni con ripetizione di A di classe 2 sono $C_{3,2}^r=\frac{3\cdot 4}{2!}=6$
  4. $$(a,a)\ (a,b)\ (a,c)\ (b,b)\ (b,c)\ (c,c)$$
  5. Per k=3 le combinazioni con ripetizione di A di classe 3 sono $C_{3,3}^r=\frac{3\cdot 4\cdot 5}{3!}=10$
  6. $$(a,a,a)\ (a,a,b)\ (a,a,c)\ (a,b,c)\ (a,b,b)\ (a,c,c)\ (b,b,b)\ (b,b,c)\ (c,c,c)\ (c,c,b)$$

 

Vai agli esercizi

Il quaderno degli appunti
Statistica e Probabilità

Coefficiente di correlazione di Pearson

Dati due variabili quantitative X e Y, si dice coefficiente di correlazione o covarianza normalizzata di X e Y il rapporto tra la covarianza e il prod
Trigonometria

Teorema del coseno o di Carnot

Il teorema del coseno (o di Carnot) è una conseguenza del teorema delle proiezioni (visto qui) e afferma che in un triangolo qualsiasi, il quadrato d
Trigonometria

Teorema delle proiezioni

Il teorema delle proiezioni dice che in un triangolo qualsiasi la misura di un lato è uguale alla somma dei prodotti di quelle degli altri due lati p