Calcolo Combinatorio

Introduzione al calcolo combinatorio

Il calcolo combinatorio studia il numero di modi in cui è possibile raggruppare, disporre od ordinare gli elementi di un insieme finito.

Funzione fattoriale

Definizione

nn fattoriale si esprime con n!n! ed indica il prodotto dei primi nn numeri naturali, escluso lo zero. Siano 0!=10! = 1 e 1!=11! = 1, allora:

n!=n(n−1)(n−2)(n−3)...⋅2⋅1n! = n(n-1)(n-2)(n-3)...\cdot 2 \cdot 1 con n≥2n \geq 2

La definizione può essere espressa con una sorta di funzione ricorsiva:

n!=n⋅(n−1)!n! = n \cdot (n-1)!

Coefficiente binomiale

Definizione

Siano n,k∈Nn, k \in \mathbb{N} e 0<k≤n0 < k \leq n, il coefficiente binomiale di n  kn\;k:

(nk)=n!k!(n−k)!=n(n−1)⋯(n−k+1)k!\binom{n}{k} = \frac{n!}{k!(n-k)!}= \frac{n(n-1) \cdots (n-k+1)}{k!}

Formula di ricorrenza

(nk+1)=(nk)⋅n−kk+1\binom{n}{k+1}=\binom{n}{k} \cdot \frac{n-k}{k+1}

La formula di ricorrenza è utile quando si conosce il valore del coefficiente binomiale per un dato valore di kk e si devono trovare i valori delle classi successive o precedenti.

Legge della classi complementari

(nk)=(nn−k)\binom{n}{k}=\binom{n}{n-k}
Dimostrazione
(nk)=n!k!(n−k)!=n!(n−k)!⋅k!=n!(n−k)![n−(n−k)]!=(nn−k)\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n!}{(n-k)!\cdot k!}=\frac{n!}{(n-k)![n-(n-k)]!}=\binom{n}{n-k}

Altre proprietà del coefficiente binomiale

(n0)=(nn)=1(n1)=(nn+1)=n\begin{equation} \begin{split} \binom{n}{0} = & \binom{n}{n} = 1 \\ \binom{n}{1} = & \binom{n}{n+1} = n \end{split} \end{equation}
(nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
Dimostrazione
(n−1k−1)+(n−1k)=(n−1)!(k−1)!⋅(n−1−k+1)!+(n−1)!k!(n−1−k)!==(n−1)!k+n−kk!(n−k)!=n!k!(n−k)!=(nk)\begin{equation} \begin{split} \binom{n-1}{k-1} + \binom{n-1}{k} & = \frac{(n-1)!}{(k-1)! \cdot(n-1-k+1)!} + \frac{(n-1)!}{k! (n-1-k)!} = \\ \\ & = (n-1)! \frac{k + n - k}{k! (n-k)!} = \frac{n!}{k!(n-k)!} = \binom{n}{k} \end{split} \end{equation}

Disposizioni

Disposizioni semplici

Definizione

Siano n,k∈Nn, k \in \mathbb{N} e 0<k≤n0 < k \leq n, le disposizioni semplici di nn elementi di classe kk sono tutti i gruppi di kk elementi che differiscono per almeno un elemento o per l’ordine con cui gli elementi sono collocati.

Dn,k=n⋅(n−1)⋅(n−2)⋅(n−3)⋅...⋅(n−k+1)D_{n,k} = n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot ... \cdot (n-k+1)

Questa espressione può essere semplificata utilizzando i numeri fattoriali:

Dn,k=n!(n−k)!D_{n,k} = \frac{n!}{(n-k)!}
Esempio
D7,3=7⋅(7−1)⋅(7−3+1)=7⋅6⋅5=210D7,3=7!4!=7⋅6⋅5⋅4!4!=7⋅6⋅5=210\begin{align*} D_{7,3} = & 7 \cdot (7-1) \cdot (7-3+1) = 7\cdot 6 \cdot 5 = 210 \\ D_{7,3} = & \frac{7!}{4!} = \frac{7 \cdot 6 \cdot 5 \cdot 4!}{4!} = 7\cdot 6 \cdot 5 = 210 \end{align*}

Disposizioni con ripetizione

Definizione

Siano n,k∈Nn, k \in \mathbb{N} e 0<k≤n0 < k \leq n, le disposizioni con ripetizione di nn elementi di classe kk sono tutti i gruppi di kk elementi che differiscono per almeno un elemento o per l’ordine con cui gli elementi sono collocati.

Dn,k′=nkD'_{n,k} = n^k

Esempio:

D22,3′=223=10648D'_{22,3} = 22^3 = 10648

Permutazioni

Permutazioni semplici

Definizione

Sia n∈N,n≥2n \in \mathbb{N}, n \geq 2, le permutazioni semplici di nn elementi sono tutti i gruppi formati dagli nn elementi che differiscono per il loro ordine.

Pn=n!P_n = n!

Esempio Si intende trovare tutti i numeri di 6 cifre distinte si possono scrivere utilizzando gli elementi dell’insieme A={2,3,4,7,8,9}A = \{2, 3, 4, 7, 8, 9\}.

P6=6!=6⋅5⋅4⋅3⋅2⋅1=720P_6 = 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720

Permutazioni con ripetizione

Definizione Siano n,k∈N,n≥2n, k \in \mathbb{N}, n \geq 2 e 0<k≤n0 < k \leq n, le permutazioni con ripetizione di nn elementi, di cui kk ripetuti, sono tutti i gruppi formati dagli nn elementi che differiscono per il loro ordine.

Pn(k)=n!k!P^{(k)}_n = \frac{n!}{k!}

Esempio Si vuole calcolare i modi in cui 5 sedie possono essere occupate da 3 persone. Si deve quindi calcolare il numero di permutazioni di 5 elementi, 2 dei quali (le sedie vuote) sono ripetuti.

Pk(2)=5!2!=5!2!=5⋅4⋅3⋅2!2!=5⋅4⋅3=60P^{(2)}_k = \frac{5!}{2!} = \frac{5!}{2!} = \frac{5 \cdot 4 \cdot 3 \cdot 2!}{2!} = 5\cdot 4 \cdot 3 = 60

Combinazioni

Combinazioni semplici

Definizione

Siano n,k∈N−{0},0<k≤nn, k \in \mathbb{N}-\{0\}, 0 < k \leq n, le combinazioni semplici di nn elementi distinti di classe kk sono tutti i gruppi di kk elementi che differiscono per almeno un elemento ma non per l’ordine.

Cn,  k=Dn,  kPk=n⋅(n−1)⋅(n−2)⋅(n−3)⋅...⋅(n−k+1)k!=(nk)C_{n,\;k} = \frac{D_{n,\;k}}{P_k} = \frac{n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot ... \cdot (n-k+1)}{k!}=\binom{n}{k}

Esempio 1 Dato un insieme A={1,15,23,44,56}A = \{ 1, 15, 23, 44, 56\} che rappresenti i numeri di 5 bici, si vuole calcolare come queste possono essere assegnate a 2 piloti.

C5,  2=D5,  2P2=5!3!⋅12!=5⋅4⋅3!3!⋅12!=5⋅42!=202=10C_{5,\;2} = \frac{D_{5,\;2}}{P_2} = \frac{5!}{3!} \cdot \frac{1}{2!} = \frac{5 \cdot 4 \cdot 3!}{3!} \cdot \frac{1}{2!} = \frac{5 \cdot 4 }{2!} = \frac{20}{2} = 10

Si ottiene lo stesso risultato applicando alle combinazioni semplici la definizione di coefficiente binomiale:

(52)=5!2!(5−2)!=5!2!⋅3!=5⋅4⋅3!2!⋅3!=5⋅42!=202=10\binom{5}{2} = \frac{5!}{2!(5-2)!} = \frac{5!}{2! \cdot 3!} = \frac{5 \cdot 4 \cdot 3!}{2! \cdot 3!} = \frac{5 \cdot 4}{2!} = \frac{20}{2} = 10

Esempio 2 Calcolare il numero di strette di mano che si scambiano 6 persone che partecipano ad una riunione di lavoro.

C5,  2=D6,  2P2=5!4!⋅12!=6⋅5⋅4!4!⋅12!=6⋅52!=302=15C_{5,\;2} = \frac{D_{6,\;2}}{P_2} = \frac{5!}{4!} \cdot \frac{1}{2!} = \frac{6 \cdot 5 \cdot 4!}{4!} \cdot \frac{1}{2!} = \frac{6 \cdot 5}{2!} = \frac{30}{2} = 15
(62)=6!2!(6−2)!=6!2!⋅4!=6⋅5⋅4!2!⋅4!=6⋅52=302=15\binom{6}{2} = \frac{6!}{2!(6 - 2)!} = \frac{6!}{2! \cdot 4!} = \frac{6 \cdot 5 \cdot 4!}{2! \cdot 4!} = \frac{6 \cdot 5}{2} = \frac{30}{2} = 15

Combinazioni con ripetizione

Definizione

Siano n,k∈N−{0},0<k≤nn, k \in \mathbb{N}-\{0\}, 0 < k \leq n, le combinazioni con ripetizione di nn elementi distinti di classe kk sono tutti i gruppi di kk elementi che soddisfino i seguenti requisiti:

  1. ogni elemento può essere ripetuto fino a kk volte
  2. l’ordine con cui si presentano gli elementi non ha importanza
  3. il numero di volte che il quale un elemento compare è diverso
Cn,  k′=Cn+k−1,  k=n⋅(n+k−1)⋅(n+k−2)...⋅(n+1)k!=(n+k−1k)C'_{n,\;k} = C_{n+k-1,\;k} = \frac{n \cdot (n+k-1) \cdot (n+k-2) ... \cdot (n+1)}{k!}=\binom{n+k-1}{k}

Esempio Si vuole calcolare in quanti modi diversi si possono distribuire 6 libri in 4 scaffali diversi.

N.B. Alcuni scaffali possono rimanere vuoti.

C4,  6′=(4+6−16)=(96)=9!6!⋅(9−6)!=9!6!⋅3!==9⋅8⋅7⋅6!6!⋅3!=9⋅8⋅73!=5046=84\begin{equation} \begin{split} C'_{4,\;6} = & \binom{4+6-1}{6} = \binom{9}{6} = \frac{9!}{6! \cdot (9-6)!} = \frac{9!}{6! \cdot 3!} = \\ & = \frac{9 \cdot 8 \cdot 7 \cdot 6!}{6! \cdot 3!} = \frac{9 \cdot 8 \cdot 7}{3!} = \frac{504}{6} = 84 \end{split} \end{equation}

Triangolo di Tartaglia (o di Pascal)

Binomio di Newton

Siano a,  b∈Ra, \; b \in \R e n∈Nn \in \N, per calcolare le potenze di un binomio con esponente n>3n > 3, si ricorre al triangolo di Tartaglia. I lati obliqui del triangolo sono formati da diversi 11, mentre ogni coefficiente interno è la somma dei due coefficienti della riga precedente che sono alla sua destra e alla sua sinistra. La potenza con esponente nn ha il seguente sviluppo:

(a+b)n=(...)anb0+(...)an−1b1+...+a0bn(a+b)^n = (...)a^n b^0 + (...)a^{n-1} b^1 + ... + a^0 b^n

Siano (...)(...) i coefficienti dell’n-esima riga. Si prenda come esempio n=4n = 4:

(a+b)4=1a4b0+4a3b1+6a2b2+4ab3+b4(a+b)^4 = 1a^4 b^0 + 4a^3 b^1 + 6a^2 b^2 + 4ab^3 + b^4

Si indichi con kk la posizione di un numero della riga e sia k=0k = 0 il primo numero a sinistra. La k-esima posizione dell’n-esima riga è occupata dal numero che corrisponde al coefficiente binomiale (nk)\binom{n}{k}

I coefficienti binomiali si possono usare per lo sviluppo di (a+b)n(a+b)^n ottenendo la formula del binomio di Newton:

(a+b)n=(n0)anb0+(n1)an−1b1+...+(nn−1)a1bn−1+(nn)a0bn(a+b)^n = \binom{n}{0}a^n b^0 + \binom{n}{1}a^{n-1} b^1 + ... + \binom{n}{n-1}a^1 b^{n-1} + \binom{n}{n}a^0 b^n

La formula può essere scritta più sinteticamente utilizzando il simbolo della sommatoria: si ricordi infatti che ∑k=0n\sum\limits_{k=0}^n significa somma dei termini che si ottengono quando k varia da 0 a n, allora la formula del binomio di Newton è riscritta come segue:

(a+b)n=∑k=0n(nk)an−kbk(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}a^{n-k}b^k
Esempio
(a+b)6==(60)a6+(61)a5b+(62)a4b2+(63)a3b3+(64)a2b4+(65)ab5+(66)b6==a6+6a5b+15a4b2+20a3b3+15a2b4+6ab5+b6\begin{equation} \begin{split} (a+b)^6 = \\ & = \binom{6}{0}a^6 + \binom{6}{1}a^5 b + \binom{6}{2}a^4 b^2 + \binom{6}{3}a^3 b^3 + \binom{6}{4}a^2 b^4 + \binom{6}{5}a b^5 + \binom{6}{6}b^6 = \\ \\ & = a^6 + 6a^5 b + 15a^4 b^2 + 20a^3 b^3 + 15a^2 b^4 + 6a b^5 + b^6 \end{split} \end{equation}

Il quadrato ed il cubo di un binomio

Si dimostri la risoluzione del quadrato di un binomio secondo la formula del binomio di Newton.

(a+b)2==(20)a2b0+(21)a1b1+(22)a0b2==1⋅a2b0+2⋅a1b1+1⋅a0b2==a2+2ab+b2\begin{equation} \begin{split} (a+b)^2 = \\ & = \binom{2}{0}a^2 b^0 + \binom{2}{1}a^1 b^1 + \binom{2}{2}a^0 b^2 = \\ \\ & = 1 \cdot a^2 b^0 + 2 \cdot a^1 b^1 + 1 \cdot a^0 b^2 = \\ \\ & = a^2 + 2ab + b^2 \end{split} \end{equation}

Si dimostri la risoluzione del cubo di un binomio secondo la formula del binomio di Newton.

(a+b)3==(30)a3b0+(31)a2b1+(32)a1b2+(33)a0b3==1⋅a3b0+3⋅a2b1+3⋅a1b2+1⋅a0b3==a3+3a2b+3ab2+b3\begin{equation} \begin{split} (a+b)^3 = \\ & = \binom{3}{0}a^3 b^0 + \binom{3}{1}a^2 b^1 + \binom{3}{2}a^1 b^2 + \binom{3}{3}a^0 b^3 = \\ \\ & = 1 \cdot a^3 b^0 + 3 \cdot a^2 b^1 + 3 \cdot a^1 b^2 + 1 \cdot a^0 b^3 = \\ \\ & = a^3 + 3a^2 b + 3ab^2 + b^3 \end{split} \end{equation}

Dimostrazione per induzione del binomio di Newton

Si dimostri, secondo il primo principio di induzione, il binomio di Newton.

  1. n=0:n = 0:
(a+b)0=∑k=00(0k)anb0  ⟹  (a+b)0=(00)a0b0  ⟹  (a+b)0=1  ⟹  1=1\begin{equation} \begin{split} & (a + b)^0 = \sum_{k = 0}^{0}\binom{0}{k} a^n b^0 \\ \\ \implies & (a + b)^0 = \binom{0}{0}a^0 b^0 \\ \\ \implies & (a + b)^0 = 1 \\ \\ \implies & 1 = 1 \end{split} \end{equation}
  1. Si supponga vera la tesi per nn e si dimostri per n+1n+1 che:
(a+b)n+1=(a+b)n⋅(a+b)(a+b)^{n+1} = (a+b)^n \cdot (a+b)
(a+b)n⋅(a+b)==(a+b)n∑k=0n(nk)an−k  bk==∑k=0n(nk)an+1−k  bk+∑k=0n(nk)an−k  bk+1k′=k+1=∑k=0n(nk)an+1−k  bk+∑k′=1n+1(nk′−1)an−k′+1  bk′per raccogliere le due sommatorie eˋ necessariotirare fuori    k=0    dalla prima sommatoria en+1    dalla seconda.=an+1∑k=1n(nk)an+1−k  bk+bn+1+∑k=1n(nk−1)an−k+1  bk==an+1+bn+1∑k=1n[(nk)+(nk−1)]an+1−k  bk==an+1+bn+1∑k=1n(n+1k)an+1−k  bk==∑k=0n+1(n+1k)an+1−k  bk\begin{equation} \begin{split} (a+b)^n \cdot (a+b) &=\\ &= (a+b)^n \sum_{k=0}^{n} \binom{n}{k} a^{n-k} \; b^k = \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} \; b^k + \sum_{k=0}^{n} \binom{n}{k} a^{n-k} \; b^{k+1} \\ & k' = k + 1\\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} \; b^k + \sum_{k' = 1}^{n+1} \binom{n}{k'-1} a^{n-k'+1} \; b^{k'} \\ \\ & \text{per raccogliere le due sommatorie è necessario} \\ & \text{tirare fuori} \; \; k = 0 \; \; \text{dalla prima sommatoria e} \\ & n + 1 \; \; \text{dalla seconda.} \\ &= a^{n+1} \sum_{k = 1}^{n} \binom{n}{k} a^{n+1-k} \; b^k + b^{n+1} + \sum_{k = 1}^{n} \binom{n}{k-1} a^{n-k+1} \; b^{k} =\\ &=a^{n+1} + b^{n+1} \sum_{k = 1}^{n} \left[ \binom{n}{k} + \binom{n}{k-1} \right] a^{n+1-k} \; b^k =\\ &=a^{n+1} + b^{n+1} \sum_{k = 1}^{n} \binom{n+1}{k} a^{n+1-k} \; b^k =\\ &=\sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} \; b^k \end{split} \end{equation}

Formula di Stifel

Definizione

Nel triangolo di Tartaglia, ogni coefficiente è la somma dei due coefficienti della riga precedente a destra e sinistra.

(nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}