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

1. [math]\displaystyle{ \binom{n}{k} = \binom{n}{n-k} }[/math]
2. [math]\displaystyle{ {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} }[/math]
3. [math]\displaystyle{ \sum_{k=0}^n \binom{n}{k} = 2^n }[/math]
4. [math]\displaystyle{ \sum_{k=0}^n \binom{n}{k} (-1)^k = 0 }[/math]
5. [math]\displaystyle{ \sum_{k=0}^m \binom{n+k}{n} = \binom{n+m+1}{n+1} = \binom{n+m+1}{m} }[/math]
6. [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]

Algunes propietats més extretes del llibre "Combinatorics":

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{ \sum_{i=0}^k (-1)^i \binom{k}{i} (k-i)^n }[/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]

Desarranjaments

Són permutacions sense punts fixos.

[math]\displaystyle{ D_n = \{ \sigma \in S_n : \sigma(i) \neq i \; \forall i \in {1, \ldots, n} \} }[/math]

Factors primers

[math]\displaystyle{ \phi(n) = \#\{ x \in [n] : (x, n) = 1 \} }[/math]

Si [math]\displaystyle{ p_1, \ldots, p_k }[/math] són els factors primers de n:

[math]\displaystyle{ \phi(n) = n(1 - \frac{1}{p_1}) \cdots (1 - \frac{1}{p_k}) }[/math]

Comptar particions

Una partició de [math]\displaystyle{ [n] = \{ 1, 2, \ldots, n \} }[/math] és expressar [math]\displaystyle{ [n] = B_1 \cup B_2 \cup \ldots \cup B_k }[/math] tq

1. [math]\displaystyle{ B_i \neq \emptyset }[/math]
2. [math]\displaystyle{ B_i \cap B_j = \emptyset \; \forall i \neq j }[/math]

Nombres de Bell

[math]\displaystyle{ B(n) = \# \text{ de particions del conjunt } [n] }[/math]

Nombres de Stirling de segona classe

[math]\displaystyle{ {n \brace k} = \# \text{ de particions de } [n] \text{ en exactament k blocs} }[/math]

Propietats

Lligam entre els nombres de Bell i els de Stirling de 2ª classe:

1. [math]\displaystyle{ B(n) = \sum_{k=1}^n {n \brace k} }[/math]

Fòrmules tancades per alguns nombres de Stirling de 2ª classe:

1. [math]\displaystyle{ {n \brace 1} = 1 = {n \brace n} }[/math]
2. [math]\displaystyle{ {n \brace n-1} = {n \choose 2} }[/math]
3. [math]\displaystyle{ {n \brace 2} = 2^{n-1} - 1 }[/math]

Propietats dels nombres de Bell i de Stirling de 2ª classe:

1. [math]\displaystyle{ {n \brace k} = {n-1 \brace k-1} + k{n-1 \brace k} }[/math]
2. [math]\displaystyle{ {n \brace k} = \frac{1}{k!} \cdot \sum_{j=0}^k (-1)^{k-j} {k \choose j} j^n }[/math]
3. [math]\displaystyle{ B(n+1) = \sum_{k=0}^n {n \choose k} B(k), B(0) = 1 }[/math]