Calcolo combinatorio

# Calcolo combinatorio ###### tags: `md` #### Cardinalità ###### Definizione 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 ###### Lemma 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. ###### Corollario 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 ###### Teorema 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. ###### Osservazione 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 ###### Notazione 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}\}$ ###### Teorema 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$. ###### Notazione 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}\}$ ###### Teorema 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$. ###### Notazione 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} \}$ ###### Teorema 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 ###### Definizione 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. ###### Teorema 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)$ ###### Definizione 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$"). ###### Teorema 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 ###### Teorema 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 ###### Teorema 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.