View source for Resum pel parcial de matemàtica discreta

== Combinatòria ==

=== Seleccions ===
{| class="wikitable" style="text-align: center;"
|-
!  !! Sense repetició !! Amb repetició
|-
! Ordenades
| <math>n^{\underline{k}} = \frac{n!}{(n-k)!}</math><br>'''k-permutacions''' || <math>n^k</math><br>'''paraules'''
|-
! No ordenades
| <math>\binom{n}{k} = \frac{n!}{(n-k)!k!}</math><br>'''k-subconjunts''' || <math>{n+k-1}\choose{k}</math><br>'''k-multiconjunts'''
|}

=== Particions d'enters ===
<math>x_i \geq 0 \\ x_1 + x_2 + \ldots + x_n = k</math>

Nombre de sol·lucions a l'equació anterior: <math>\binom{n+k-1}{k}</math>

=== Teorema del binomi ===
<math>(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}</math>

==== Teorema del binomi de Newton ====
<math>(1+x)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k} x^k</math>

=== Propietats dels nombres binomials ===
# <math>\binom{n}{k} = \binom{n}{n-k}</math>
# <math>{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}</math>
# <math>\sum_{k=0}^n \binom{n}{k} = 2^n</math>
# <math>\sum_{k=0}^n \binom{n}{k} (-1)^k = 0</math>
# <math>\sum_{k=0}^m \binom{n+k}{n} = \binom{n+m+1}{n+1} = \binom{n+m+1}{m}</math>
# <math>\sum_{i=0}^k \binom{n}{i}\binom{m}{k-i} = \binom{n+m}{k}</math> (Vandermonde)
#* Si prenem <math>n=m=k</math>: <math>\binom{2n}{n} = \sum_{i=0}^n \binom{n}{i}^2</math>

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

{{under construction|avm99963}}

=== Aplicacions ===
{| class="wikitable"
|-
! <math>\#\{\text{aplicacions } f:[k] \longrightarrow [n]\}</math>
| <math>n^k</math>
|-
! <math>\text{Injectives (one-to-one)}</math>
| <math>n^\underline{k}</math>
|-
! <math>\text{Estrictament creixents}</math>
| <math>\binom{n}{k}</math>
|-
! <math>\text{Creixents}</math>
| <math>\binom{n+k-1}{k}</math>
|-
! <math>\text{Exhaustives (onto)}</math>
| <math>\sum_{i=0}^k (-1)^i \binom{k}{i} (k-i)^n</math>
|}

=== Coeficients multinomials ===
<math>\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>(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>| A_1 \cup \cdots \cup A_n | = \sum_{i=1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < 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>D_n = \{ \sigma \in S_n : \sigma(i) \neq i \; \forall i \in {1, \ldots, n} \}</math>

=== Factors primers ===
<math>\phi(n) = \#\{ x \in [n] : (x, n) = 1 \}</math>

Si <math>p_1, \ldots, p_k</math> són els factors primers de n:

<math>\phi(n) = n(1 - \frac{1}{p_1}) \cdots (1 - \frac{1}{p_k})</math>

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

# <math>B_i \neq \emptyset</math>
# <math>B_i \cap B_j = \emptyset \; \forall i \neq j</math>

==== Nombres de Bell ====
<math>B(n) = \# \text{ de particions del conjunt } [n]</math>

==== Nombres de Stirling de segona classe ====
<math>{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:
# <math>B(n) = \sum_{k=1}^n {n \brace k}</math>

Fòrmules tancades per alguns nombres de Stirling de 2ª classe:
# <math>{n \brace 1} = 1 = {n \brace n}</math>
# <math>{n \brace n-1} = {n \choose 2}</math>
# <math>{n \brace 2} = 2^{n-1} - 1</math>

Propietats dels nombres de Bell i de Stirling de 2ª classe:
# <math>{n \brace k} = {n-1 \brace k-1} + k{n-1 \brace k}</math>
# <math>{n \brace k} = \frac{1}{k!} \cdot \sum_{j=0}^k (-1)^{k-j} {k \choose j} j^n</math>
# <math>B(n+1) = \sum_{k=0}^n {n \choose k} B(k), B(0) = 1</math>