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]

[math]\displaystyle{ \#D_n = n!\left(1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \ldots + (-1)^n \frac{1}{n!}\right) }[/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]

Més particions d'enters

Composicions: particions ordenades.

[math]\displaystyle{ \#\text{composicions de } n \text{ en } k \text{ sumands} = \binom{n-1}{k-1} }[/math]

[math]\displaystyle{ \#\text{total de composicions} = \sum_{k=1}^n \binom{n-1}{k-1} = 2^{n-1} }[/math]

Particions

Diagrama de Ferrers que mostra el nombre de particions dels enters de l'1 fins al 8

[math]\displaystyle{ n = \lambda_1 + \lambda_2 + \ldots + \lambda_k \quad \lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_k }[/math]

[math]\displaystyle{ p_k(n) = \#\text{particions de } n \text{ en } k \text{ parts} }[/math]

[math]\displaystyle{ p(n) = \sum_{k=1}^n p_k(n) = \#\text{particions} }[/math]

Propietats

1. [math]\displaystyle{ p_k(n) = p_{k-1}(n-1) + p_k(n-k) }[/math]
2. [math]\displaystyle{ \#\text{particions de } n \text{ en } k \text{ parts} = \# \text{particions de $n$ en què la part més gran és igual a $k$} }[/math]
3. [math]\displaystyle{ p(n |\text{autoconjugades}) = p(n | \text{parts senars i diferents}) }[/math]
4. Teorema d'Euler: [math]\displaystyle{ p(n | \text{parts senars}) = p(n | \text{parts diferents}) }[/math]
5. [math]\displaystyle{ p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) + \ldots }[/math], on [math]\displaystyle{ n-1, n-2, n-5, \ldots }[/math] són els nombres pentagonals, és a dir, els nombres de la forma [math]\displaystyle{ \frac{k(3k \pm 1)}{2} }[/math]

Equacions recurrents

Successió de Fibonacci

Terme general: [math]\displaystyle{ F_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n }[/math]

Trobar terme general de recurrències

Proposició: Són equivalents:

1. [math]\displaystyle{ a_{n+k} + c_1a_{n+k-1} + c_2a_{n+k-2} + \ldots + c_ka_n = f(n) \; \forall n \geq 0 }[/math]
2. [math]\displaystyle{ \sum_{n=0}^\infty a_nx^n = \frac{I(x) + x^kF(x)}{1 + c_1x + \ldots + c_kx^k} \quad \text{(} I(x) \text{ polinomi de grau } \leq k-1 \text{ que depén de les condicions inicials, } F(x) = \sum_{n \geq 0}f(n)x^n \text{)} }[/math]