Resum pel parcial de matemàtica discreta
Combinatòria
Seleccions
| Sense repetició | Amb repetició | |
|---|---|---|
| Ordenades | [math]\displaystyle{ n^{\underline{k}} = \frac{n!}{(n-k)!} }[/math] k-permutacions |
[math]\displaystyle{ n^k }[/math] paraules |
| No ordenades | [math]\displaystyle{ \binom{n}{k} = \frac{n!}{(n-k)!k!} }[/math] k-subconjunts |
[math]\displaystyle{ {n+k-1}\choose{k} }[/math] k-multiconjunts |
Particions d'enters
[math]\displaystyle{ x_i \geq 0 \\ x_1 + x_2 + \ldots + x_n = k }[/math]
Nombre de sol·lucions a l'equació anterior: [math]\displaystyle{ \binom{n+k-1}{k} }[/math]
Teorema del binomi
[math]\displaystyle{ (x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k} }[/math]
Teorema del binomi de Newton
[math]\displaystyle{ (1+x)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k} x^k }[/math]
Propietats dels nombres binomials
- [math]\displaystyle{ \binom{n}{k} = \binom{n}{n-k} }[/math]
- [math]\displaystyle{ \sum_{k=0}^n \binom{n}{k} = 2^n }[/math]
- [math]\displaystyle{ \sum_{k=0}^n \binom{n}{k} (-1)^k = 0 }[/math]
- [math]\displaystyle{ \sum_{k=0}^m \binom{n+k}{n} = \binom{n+m+1}{n+1} = \binom{n+m+1}{m} }[/math]
- [math]\displaystyle{ \sum_{i=0}^k \binom{n}{i}\binom{m}{k-i} = \binom{n+m}{k} }[/math] (Vandermonde)
- Si prenem [math]\displaystyle{ n=m=k }[/math]: [math]\displaystyle{ \binom{2n}{n} = \sum_{i=0}^n \binom{n}{i}^2 }[/math]
Aplicacions
| [math]\displaystyle{ \#\{\text{aplicacions } f:[k] \longrightarrow [n]\} }[/math] | [math]\displaystyle{ n^k }[/math] |
|---|---|
| [math]\displaystyle{ \text{Injectives (one-to-one)} }[/math] | [math]\displaystyle{ n^\underline{k} }[/math] |
| [math]\displaystyle{ \text{Estrictament creixents} }[/math] | [math]\displaystyle{ \binom{n}{k} }[/math] |
| [math]\displaystyle{ \text{Creixents} }[/math] | [math]\displaystyle{ \binom{n+k-1}{k} }[/math] |
| [math]\displaystyle{ \text{Exhaustives (onto)} }[/math] | [math]\displaystyle{ ? }[/math] |
Coeficients multinomials
[math]\displaystyle{ \displaystyle \binom{n}{n_1,n_2,\ldots,n_s} = \frac{n!}{n_1! n_2! \cdots n_s!} = \binom{n}{n_1} \binom{n - n_1}{n_2} \binom{n - n_1 - n_2}{n_3} \cdots \binom{n - n_1 - n_2 - \ldots - n_{s-1}}{n_s} }[/math]
Teorema del multinomi
[math]\displaystyle{ (x_1 + \ldots x_k)^n = \sum_{n_i \geq 0 \\ n_1 + \ldots + n_k = n} \binom{n}{n_1, n_2, \ldots, n_k}x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k} }[/math]
Principi d'inclusió-exclusió
[math]\displaystyle{ | A_1 \cup \cdots \cup A_n | = \sum_{i=1}^n |A_i| - \sum_{1 \leq i \lt j \leq n} |A_i \cap A_j| + \sum_{1 \leq i \lt j \lt k \leq n} |A_i \cap A_j \cap A_k| - \ldots + (-1)^{n+1}|A_1 \cap A_2 \cap \cdots \cap A_n| }[/math]
