---
# System prepended metadata

title: Calcolo combinatorio
tags: [md]

---

# Calcolo combinatorio
###### tags: `md`
#### Cardinalità

###### <span style="color: #e53935">Definizione</span>

Un insieme $X$ è finito di cardinalità $n \in \mathbb{N}-\{0\}$ quando esiste una funzione bigettiva $g : X\to\mathbb{N}_n$, e si scrive $|X|=n$

L'insieme vuoto è un insieme finito la cui cardinalità si pone uguale a 0, e si scrive $|\emptyset|=0$

Se un insieme non vuoto Y è tale che per nessun $n \in \mathbb{N}-\{0\}$ esiste una funzione bigettiva da $Y$ a $\mathbb{N}_n$ allora si dice che $Y$ è infinito.

#### Lemma dei cassetti

###### <span style="color: #00897b">Lemma</span>

Supponiamo di avere una funzione $h : \mathbb{N}_n\to\mathbb{N}_m$ con $n>m$. Allora $h$ non è iniettiva.

Enunciato generale
Supponiamo di avere una funzione $f : X \to Y$ , dove $X$ è un insieme di cardinalità $n$ e $Y$ è un insieme di cardinalità $m$, con $n > m$. Allora f non è iniettiva.

###### <span style="color: #388e3c">Corollario</span>

Se $N$ oggetti sono sistemati in K scatole, allora c'è (almeno) una scatola che contiene almeno $\left\lceil \frac{N}{K} \right\rceil$ oggetti (qui $\left\lceil \frac{N}{K} \right\rceil$ è la ”parte intera superiore” di $\frac{N}{K}$, ossia il più piccolo numero intero $\ge \frac{N}{K}$).

#### Applicazioni

###### <span style="color: #0288d1">Teorema</span>

Supponiamo che $X$ e $Y$ siano insiemi tali che $X \subseteq Y$ e $Y$ sia finito. Allora anche $X$ è finito e $|X|\le|Y|$

Supponiamo che $f : X \to Y$ sia una funzione fra insiemi ﬁniti e non vuoti tali che $|X| < |Y|$. Allora $f$ non è surgettiva. 

Supponiamo che $X$ e $Y$ siano insiemi ﬁniti non vuoti della stessa cardinalità. Allora una funzione $f : X \to Y$ è iniettiva se e solo se è surgettiva. 

###### <span style="color: #ffc107">Osservazione</span>

Dunque, in questo caso dove $|X| = |Y|$, per provare che una certa funzione $g : X \to Y$ è bigettiva basta provare una sola fra queste due proprietà: $g$ è iniettiva o $g$ è surgettiva.

#### Insiemi di funzioni

###### <span style="color: #ce93d8">Notazione</span>

Siano $X$ e $Y$ due insiemi. Chiamiamo$ F(X \to Y )$ l'insieme di tutte le funzioni che hanno $X$ come dominio e $Y$ come codominio: $F(X \to Y) = \{f |f : X \to Y \text{ è una funzione}\}$

###### <span style="color: #0288d1">Teorema</span>

Siano $X$ e $Y$ ﬁniti non vuoti con $|X| = n$ e $|Y| = m$. Allora $|F(X \to Y)| = m^n$

###### Dimostrazione

Sia $X=\{x_1,x_2,\ldots, x_n\}$ e $Y=\{y_1,y_2,\ldots, y_m\}$.
Proviamo a costruire una funzione da $X$ a $Y$.
Dove mandiamo $x_1$? Abbiamo $m$ scelte: $y_1,y_2,\ldots,y_m$. 
Dove mandiamo $x_2$? Abbiamo sempre $m$ scelte: $y_1,y_2,\ldots, y_m$, perché non abbiamo fatto nessuna richiesta sulla funzione (tipo "che sia iniettiva" o "surgettiva" etc...). In generale, dove mandiamo $x_i$ con $i= 1,2,\ldots,n$? Abbiamo sempre $m$ scelte. Dunque alla fine possiamo costruire la nostra funzione in $\underbrace{m\cdot m\cdot m\cdots m}_{\text{n volte}}=m^n$ modi diversi. 
Siccome ci capiterà di ripetere spesso ragionamenti simili a questo, vale la pena soffermarsi e riscrivere la dimostrazione da un altro punto di vista.

###### Dimostrazione

In realtà individuare una funzione $f:X\to Y$ equivale ad individuare un elemento del prodotto cartesiano $\underbrace{Y\times Y\times \cdots \times Y}_{\text{n volte}}=Y^n$. Infatti un elemento di $Y^n$ è una lista $(a_1,a_2,\ldots,a_n)$ di elementi di $Y$ e per ogni tale lista noi possiamo porre $f(x_1) =a_1, \quad f(x_2) =a_2,\quad \ldots,\quad f(x_n) =a_n$.  Viceversa, data una funzione $f:X\to Y$possiamo costruire l'elemento $(f(x_1),f(x_2),\ldots,f(x_n))\in Y_n$. Dunque vale$|F(X\to Y)|=|Y_n|$ e noi abbiamo già osservato che $|Y^n|=m^n$.

###### <span style="color: #ce93d8">Notazione</span>

Chiamiamo $Inj (X \to Y)$ l'insieme di tutte le funzioni iniettive che hanno $X$ come dominio e $Y$ come codominio:$ Inj (X \to Y) = \{f | f : X \to Y \text{è una funzione iniettiva}\}$ 

###### <span style="color: #0288d1">Teorema</span>

Siano $X$ e $Y$ ﬁniti non vuoti con $|X| = n$ e $|Y| = m$. Allora $|Inj(X → Y)| = m(m−1)(m−2)\cdots(m−n + 1)$

###### Dimostrazione

Sia $X=\{x_1,x_2,\ldots, x_n\}$ e $Y=\{y_1,y_2,\ldots, y_m\}$. Se $n > m$ il lemma dei Cassetti ci dice che$|Inj(X\to Y)|= 0$. Supponiamo allora $n\le m$ e proviamo a costruire una funzione iniettiva $g$ da $X$a $Y$. 
Dove mandiamo $x_1$? Abbiamo $m$ scelte: $y_1,y_2,\ldots, y_m$. 
Dove mandiamox2? Abbiamo $m−1$ scelte, ossia gli elementi di $Y−\{g(x_1)\}$, visto chela funzione deve essere iniettiva. 
In generale, dove mandiamo $x_i$ con $i= 1,2,\ldots,n$? Abbiamo $m−(i−1)$ scelte, cioè gli elementi di $Y−\{g(x_1),g(x_2),\ldots,g(x_i−1)\}$. In particolare per l'ultimo elemento $x_n$ avremo $m−(n−1)$ scelte. Dunque alla fine possiamo costruire la nostra funzione in $m\cdot (m−1)\cdot (m−2)\cdots (m−n+ 1)$ modi diversi. Come ultima osservazione notiamo che la formula ottenuta vale per ogni $m$ e ogni $n$ interi positivi, ossia $|Inj(X→Y)|=m(m−1)(m−2)\cdots(m−n+ 1)$ si adatta bene anche al caso in cui $n > m$: in tal caso infatti la nostra formula è un prodotto di fattori fra i quali è presente anche $m−m$ e dunque ha come risultato $0$ che,come abbiamo osservato all'inizio, è proprio il numero di funzioni iniettive da $X$ a $Y$.

###### <span style="color: #ce93d8">Notazione</span>

Se $|X| = |Y|$ allora l'insieme delle funzioni bigettive che hanno $X$ come dominio e $Y$ come codominio è non vuoto: 
$Bij (X \to Y): Bij (X \to Y) = \{ f | f : X \to Y \text{ è una funzione bigettiva} \}$

###### <span style="color: #0288d1">Teorema</span>

Siano $X$ e $Y$ ﬁniti non vuoti con $|X| = |Y| = n$. Allora $|Bij (X \to Y)| = n!$

###### Dimostrazione

Visto che $|X|=|Y|$ allora $Bij(X\to Y) =Inj(X\to Y )$ e dunque si tratta solo di porre $n=m$ nell'enunciato del teorema precedente.

#### Cardinalità insieme delle parti

###### <span style="color: #e53935">Definizione</span>

L'insieme $\mathcal{P}(A)$ delle parti di $A$ è l'insieme i cui elementi sono tutti i sottoinsiemi di A: $\mathcal{P}(A) = {B|B \sube A}$

Osserviamo in particolare che $A \in \mathcal{P}(A)$ e $\emptyset \in \mathcal{P}(A)$. In questo paragrafo vogliamo contare quanti elementi ha $\mathcal{P}(A)$ nel caso in cui $A$ sia un insieme ﬁnito.

###### <span style="color: #0288d1">Teorema</span>

Se $|A| = n$ allora $|\mathcal{P}(A)| = 2^n$ 

###### Dimostrazione

Se $A=\emptyset$ allora ho solo un sottoinsieme, e la formula torna. Se $|A| \ge 1$, per contare quanti sono i sottoinsiemi di $A$ immaginiamo di doverne costruire uno.  Osserviamo che per individuare un sottoinsieme basta sapere, per ognuno degli $n$ elementi di $A$, se tale elemento appartiene o no al sottoinsieme.  Possiamo dunque passare in rassegna gli elementi di $A$ e per ognuno di loro abbiamo due scelte: SI (sta nel sottoinsieme) oppure NO. 
Dunque ci sono $2^n$ distinti sottoinsiemi di $A$. Osserviamo che l'insieme vuoto corrisponde al caso in cui abbiamo ricevuto sempre la risposta NO e l'insieme $A$ al caso in cui abbiamo ricevuto sempre la risposta SI.

`nelle dispense c'è anche una dimostrazione a pagina 69 molto lunga basata sul'induzione`

#### Coefficiente binomiale

Dato un insieme $X$ ﬁnito o inﬁnito, costruiamo dei particolari sottoinsiemi del suo insieme delle parti $\mathcal{P}(X)$

###### <span style="color: #e53935">Definizione</span>

Dato $r \to N$, chiamiamo $\mathcal{P}_r(X)$ l’insieme i cui elementi sono tutti i sottoinsiemi di $X$ che hanno cardinalità $r$:
$$
\mathcal{P}_r(X) = \{A|A \sube X \land |A| = r\}​
$$
Indicheremo $|\mathcal{P}_r(X)|$ con il simbolo ${n \choose r}$ (si legge: "coeﬃciente binomiale $n$ su $r$").

###### <span style="color: #0288d1">Teorema</span>

Dati $n,r \in N$, con $0 \le r \le n$, vale che

$$
{n \choose r} = 
{n (n−1) (n−2) ···(n−r + 1) \over r!} =
{n! \over r! (n−r)!}
$$

###### Dimostrazione

Come prima, fissato un insieme $X$ con $n$ elementi, cerchiamo di contare la cardinalità di $\mathcal{P}_r(X)$. 
Consideriamo $\mathbb{N}_r=\{1,2,3,\ldots ,r\}$ e una funzione iniettiva
$$
f:\mathbb{N}_r\to X
$$
Chi è $Imm(f=)$? È un sottoinsieme di $X$ di cardinalità $r$, dunque è un elemento di $\mathcal{P}_r(X)$, proprio uno di quelli che dobbiamo "contare". Sarà vero che ogni elemento di $\mathcal{P}_r(X)$ lo posso esprimere come immagine di una funzione iniettiva da $\mathbb{N}_r$ a $X$? Sì, preso infatti un elemento di $\mathcal{P}_r(X)$, cioè un sottoinsieme $\{a_1,a_2,\ldots,a_r\} \subseteq X$, posso facilmente indicare una funzione iniettiva da $\mathbb{N}_r$ a $X$ la cui immagine sia proprio $\{a_1,a_2,\ldots,a_r\}$: per esempio posso prendere la $g:\mathbb{N}_r\to X$ definita da $g(1) =a_1, \; g(2) =a_2,\; \ldots,\;g(r) =a_r$. Insomma, con le funzioni iniettive da $\mathbb{N}_r$ a $X$ "raggiungiamo" tutti gli elementi di $\mathcal{P}_r(X)$. Per trovare $|\mathcal{P}_r(X)|$ potremmo allora cominciare a contare $|Inj(\mathbb{N}_r\to X)|$, ossia quante sono le funzioni iniettive da $\mathbb{N}_r$ a $X$. Ma questo numero lo abbiamo già calcolato: è $n(n−1) (n−2)\cdots(n−r+ 1)$. È vero allora che $|\mathcal{P}_r(X)|=n(n−1) (n−2)\cdots(n−r+ 1)$?  NO, perché se scriviamo così commettiamo l'errore di contare ogni elemento di $\mathcal{P}_r(X)$ più volte. Precisamente, dato un sottoinsieme $\{a_1,a_2,\ldots,a_r\} \subseteq X$ lo stiamo contando $|Inj(\mathbb{N}_r\to\{a_1,a_2,\ldots,a_r\})|$ volte, cioè tante volte quante sono le diverse funzioni iniettive possibili da $\mathbb{N}_r$ a $\{a_1,a_2,\ldots,a_r\}$.  Ma sappiamo quanto vale$|Inj(\mathbb{N}_r\to \{a_1,a_2,\ldots,a_r\})|$: applicando la formula per il conto delle funzioni iniettive a questo caso particolare in cui dominio e codominio hanno la stessa cardinalità $r$ (dunque stiamo in realtà considerando le funzioni bigettive), troviamo che 
$$
|Inj(\mathbb{N}_r\to \{a_1,a_2,\ldots,a_r\})|=|Bij(\mathbb{N}_r\to \{a_1,a_2,\ldots,a_r\})|=r!
$$
Allora, visto che col numero $n(n−1) (n−2)\cdots (n−r+ 1)$ abbiamo contato $r!$ volte ogni elemento di $\mathcal{P}_r(X)$, per avere $|\mathcal{P}_r(X)|$ basterà dividerlo per $r!$:
$$
(nr)=|\mathcal{P}r(X)|={n(n−1) (n−2)\cdots(n−r+ 1) \over r!}
$$


#### Triangolo di Pascal-Tartaglia

###### <span style="color: #0288d1">Teorema</span>

Dati $r,n ∈N^+$ con$ 1 ≤ r < n$, vale

$$
{n \choose r} =
{n−1 \choose r−1} + {n−1 \choose r}
$$

###### Dimostrazione

Sia $X$ un insieme con $n$ elementi.  Visto che $n\ge 1$, possiamo scegliere un elemento $a\in X$.  Per calcolare $n\choose r$ dobbiamo calcolare la cardinalità di $\mathcal{P}_r(X)$. Possiamo adesso dividere $\mathcal{P}_r(X)$ in due parti, raggruppando in un sottoinsieme (che chiameremo $L_1$) tutti i sottoinsiemi di $X$ di cardinalità $r$ che contengono $a$, e in un altro (che chiameremo $L_2$) tutti i sottoinsiemi di $X$ di cardinalità $r$ che NON contengono $a$: $\mathcal{P}_r(X) =L_1\cup L_2$
Trattandosi di una unione di due insiemi disgiunti, vale che
$$
n\choose r=|\mathcal{P}_r(X)|=|L_1|+|L_2|
$$
Ora, un sottoinsieme di cardinalità $r$ che contiene $a$ è univocamente determinato se si dice quali sono gli altri elementi (quelli diversi da $a$) che contiene; tali elementi costituiscono un sottoinsieme di cardinalità $r−1$ di $X−\{a\}$. Dunque
$$
|L_1|=|\mathcal{P}_{r−1}(X−\{a\})|={n−1 \choose r−1}
$$
Analogamente si osserva che scegliere un sottoinsieme di $X$ di cardinalità $r$ che non contiene $a$ equivale a scegliere un sottoinsieme di $X−\{a\}$ di cardinalità $r$, dunque
$$
|L_2|=|\mathcal{P}_r(X−\{a\})|={n−1 \choose r}
$$
Allora possiamo concludere che
$$
{n \choose r}=|\mathcal{P}_r(X)|=|L_1|+|L_2|={n−1\choose r−1}+{n−1\choose r}
$$
Il teorema che abbiamo appena dimostrato è il motivo per cui possiamo disporre i coefficienti binomiali in modo da formare il cosiddetto "Triangolo di Pascal-Tartaglia"

#### Teorema del binomio di Newton

###### <span style="color: #0288d1">Teorema</span>

Date due variabili $a$ e $b$, per ogni $n \to N$ vale: 

$$
(a + b)^n = \sum_{i=0}^n {n \choose i} a^{n−i}b^i
$$

cioè

$$
(a + b)^n = 
{n \choose 0}a^n + 
{n \choose 1}a^{n−1}b^1 + 
{n \choose 2}a^{n−2}b^2 + 
\cdots +
{n \choose n−1}a^1b^{n−1} +
{n \choose n}b^n
$$

###### Dimostrazione

Cominciamo da un esempio, per avere un'idea di cosa succede. Calcoliamo lo sviluppo di $(a+b)^3$. Se non raggruppiamo i termini troviamo: 
$$
(a+b)^3= (a+b)(a+b)(a+b) =a(a+b)(a+b) +b(a+b)(a+b) =\\=
aa(a+b) +ab(a+b) +ba(a+b) +bb(a+b) = \\=
aaa+aab+aba+abb+baa+bab+bba+bbb
$$
Abbiamo espresso $(a+b)^3$ come somma di $8$ monomi, ognuno dei quali è stato ottenuto, tramite le proprietà distributiva e associativa, scegliendo o $a$ o $b$ da ogni parentesi che compare in $(a+b)(a+b)(a+b)$. Quindi, raggruppando adesso i termini tramite la proprietà commutativa, quale sarà il coefficiente di $a^2b$? Sarà uguale al numero dei monomi in cui troviamo due $a$ e una $b$. E questi quanti sono? Sono $3 ={3\choose 2}$, ossia sono tanti quanti sono i modi di scegliere due parentesi fra le tre del prodotto $(a+b)(a+b)(a+b)$ (queste saranno le parentesi da cui prendo la $a$): la prima e la seconda, la prima e la terza, la seconda e la terza. Dunque nello sviluppo avremo $3a^2b$. Ovviamente, saremmo arrivati allo stesso risultato contando i modi di scegliere una parentesi fra le tre del prodotto $(a+b)(a+b)(a+b)$ (quella da cui prendo la $b$), perché ${3\choose 1}={3\choose 2}= 3$. Passiamo al caso generale. Nello sviluppo di $(a+b)^n$ troveremo $2^n$ monomi, ciascuno ottenuto scegliendo o $a$ o $b$ da ognuna delle $n$ parentesi del prodotto 
$$
(a+b)^n= (a+b)(a+b)(a+b)\cdots(a+b)(a+b)
$$
Raggruppando i termini, preso un indice $i$ con $0\le i\le n$, quale sarà allora il coefficiente di $a^{n−i}b^i$? Sarà uguale al numero di modi con cui si possono scegliere $i$ parentesi fra le $n$ del prodotto $(a+b)(a+b)(a+b)\cdots(a+b)(a+b)$ (quelle da cui prendiamo la $b$); dunque sarà uguale a $n\choose i$. Oppure sarà uguale al numero di modi con cui si possono scegliere $n−i$ parentesi fra le $n$ del prodotto $(a+b)(a+b)(a+b)\cdots(a+b)(a+b)$ (quelle da cui prendiamo la $a$): infatti come sappiamo ${n\choose i}={n\choose n−i}$. In conclusione, nello sviluppo di $(a+b)^n$ troveremo il termine ${n\choose i}a^{n−i}b^i$. Siccome questo è vero per ogni $i$, con $0\le i\le n$, abbiamo dimostrato il teorema.