calcolo combinatorio in breve

Panoramica

Per contare il numero di elementi di insiemi a partire da altri insiemi.

---

1- Se $A$ insieme di $n$ elementi e $B$ insieme di $m$ elementi, scriviamo

$|A|=n,|B|=m$

allora

$|A\times B|=n\cdot m$

---

2- $|A|=n,|B|=m$,
il numero delle funzioni da a $A$ a $B$

$B^A=$ {numero delle funzioni da a $A$ a $B$}

$|B^A|=|B{|}^{|A|}=m^n$

sono disposizioni con ripetizione

---

3- $|A|=n,|B|=m$ con $m\ge n$,

$D=$ {funzioni iniettive da $A$ a $B}

$|D|=m(m-1)(m-2)\dots (m-n+1)$

sono disposizioni di m oggetti a n a n

---

4- $|A|=|B|=n$, funzioni biettive tra $A$ e $B$

$P=$ {biezioni da $A$ in sé stesso}

$|P|=n(n-1)(n-2)\dots (2)(1)(0!)=n!$

sono permutazioni di n oggetti

---

5- Sia $|A|=n$, $0\le k\le n$,
il numero dei sottoinsiemi di $A$ con $k$ elementi

$C_k^n=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$ {numero dei sottoinsiemi di $A$ con $k$ elementi}

sono combinazioni di n oggetti a k a k

---

Osservazione
$D=C_k^n\cdot k!$
sono le combinazioni di n oggetti a k a k ordinate, ognuna genera $k!$ disposizioni.

Il coefficiente binomiale

$\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$

$\left(\genfrac{}{}{0ex}{}{n}{0}\right)=1$

$\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$

Dimostrabile con gli insiemi o con la formula

Per $1\le k\le n-1$
$\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$

Dimostrabile con gli insiemi o con la formula

Triangolo di Tartaglia

$$\begin{array}{cccccccccccc}& & & & & & 1& & & & & \\ & & & & & 1& & 1& & & & \\ & & & & 1& & 2& & 1& & & \\ & & & 1& & 3& & 3& & 1& & \\ & & 1& & 4& & 6& & 4& & 1& \\ & 1& & 5& & 10& & 10& & 5& & 1\end{array}$$ $$\begin{array}{cccccccccccc}& & & & & & \left(\genfrac{}{}{0ex}{}{0}{0}\right)& & & & & \\ & & & & & \left(\genfrac{}{}{0ex}{}{1}{0}\right)& & \left(\genfrac{}{}{0ex}{}{1}{1}\right)& & & & \\ & & & & \left(\genfrac{}{}{0ex}{}{2}{0}\right)& & \left(\genfrac{}{}{0ex}{}{2}{1}\right)& & \left(\genfrac{}{}{0ex}{}{2}{2}\right)& & & \\ & & & \left(\genfrac{}{}{0ex}{}{3}{0}\right)& & \left(\genfrac{}{}{0ex}{}{3}{1}\right)& & \left(\genfrac{}{}{0ex}{}{3}{2}\right)& & \left(\genfrac{}{}{0ex}{}{3}{3}\right)& & \\ & & \left(\genfrac{}{}{0ex}{}{4}{0}\right)& & \left(\genfrac{}{}{0ex}{}{4}{1}\right)& & \left(\genfrac{}{}{0ex}{}{4}{2}\right)& & \left(\genfrac{}{}{0ex}{}{4}{3}\right)& & \left(\genfrac{}{}{0ex}{}{4}{4}\right)& \\ & \left(\genfrac{}{}{0ex}{}{5}{0}\right)& & \left(\genfrac{}{}{0ex}{}{5}{1}\right)& & \left(\genfrac{}{}{0ex}{}{5}{2}\right)& & \left(\genfrac{}{}{0ex}{}{5}{3}\right)& & \left(\genfrac{}{}{0ex}{}{5}{4}\right)& & \left(\genfrac{}{}{0ex}{}{5}{5}\right)\end{array}$$

Teorema del binomio di Newton

Siano $a,b\in \mathbb{R}$ (o $\in \mathbb{C}$),
sia $n\in \mathbb{N},n\ge 1$

allora $(a+b{)}^n=\sum _{j=o}^n(\genfrac{}{}{0ex}{}{n}{j})a^{n-j}{b}^j$

Dimostrabile con l’induzione

Osservazione
$\sum _{j=o}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)=2^n$
che sono tutti i sottoinsiemi possibili

Dimostrabile con $(1+1{)}^n$

Osservazione
$\sum _{j=o}^n(-1{)}^j(\genfrac{}{}{0ex}{}{n}{j})=0$
che sono tutti i sottoinsiemi possibili

Dimostrabile con $(1-1{)}^n$

calcolo combinatorio

Risorse