709
edits
Difference between revisions of "Resum pel parcial de matemàtica discreta"
From Potatopedia
Resum pel parcial de matemàtica discreta (view source)
Revision as of 22:14, 28 March 2018
, 22:14, 28 March 2018Fet i revisat fins els nombres de Bell i de Stirling de segona classe
(Fet fins el principi d'inclusió-exclusió) |
(Fet i revisat fins els nombres de Bell i de Stirling de segona classe) |
||
| Line 26: | Line 26: | ||
=== Propietats dels nombres binomials === | === Propietats dels nombres binomials === | ||
# <math>\binom{n}{k} = \binom{n}{n-k}</math> | # <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} = 2^n</math> | ||
# <math>\sum_{k=0}^n \binom{n}{k} (-1)^k = 0</math> | # <math>\sum_{k=0}^n \binom{n}{k} (-1)^k = 0</math> | ||
| Line 31: | Line 32: | ||
# <math>\sum_{i=0}^k \binom{n}{i}\binom{m}{k-i} = \binom{n+m}{k}</math> (Vandermonde) | # <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> | #* 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 === | === Aplicacions === | ||
| Line 48: | Line 53: | ||
|- | |- | ||
! <math>\text{Exhaustives (onto)}</math> | ! <math>\text{Exhaustives (onto)}</math> | ||
| <math> | | <math>\sum_{i=0}^k (-1)^i \binom{k}{i} (k-i)^n</math> | ||
|} | |} | ||
| Line 58: | Line 63: | ||
=== Principi d'inclusió-exclusió === | === 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> | <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> | |||
