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 21:23, 2 April 2018
, 21:23, 2 April 2018Fet fins la part de recurrències, que no he acabat completament
(→Desarranjaments: Afegit cardinal de D_n) |
(Fet fins la part de recurrències, que no he acabat completament) |
||
| Line 103: | Line 103: | ||
# <math>{n \brace k} = {n-1 \brace k-1} + k{n-1 \brace k}</math> | # <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>{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> | # <math>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>\#\text{composicions de } n \text{ en } k \text{ sumands} = \binom{n-1}{k-1}</math> | |||
<math>\#\text{total de composicions} = \sum_{k=1}^n \binom{n-1}{k-1} = 2^{n-1}</math> | |||
==== Particions ==== | |||
[[File:Ferrer partitioning diagrams.svg|thumb|right|280px|Diagrama de Ferrers que mostra el nombre de particions dels enters de l'1 fins al 8]] | |||
<math>n = \lambda_1 + \lambda_2 + \ldots + \lambda_k \quad \lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_k</math> | |||
<math>p_k(n) = \#\text{particions de } n \text{ en } k \text{ parts}</math> | |||
<math>p(n) = \sum_{k=1}^n p_k(n) = \#\text{particions}</math> | |||
==== Propietats ==== | |||
# <math>p_k(n) = p_{k-1}(n-1) + p_k(n-k)</math> | |||
# <math>\#\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> | |||
# <math>p(n |\text{autoconjugades}) = p(n | \text{parts senars i diferents})</math> | |||
# '''Teorema d'Euler''': <math>p(n | \text{parts senars}) = p(n | \text{parts diferents})</math> | |||
# <math>p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) + \ldots</math>, on <math>n-1, n-2, n-5, \ldots</math> són els nombres pentagonals, és a dir, els nombres de la forma <math>\frac{k(3k \pm 1)}{2}</math> | |||
== Equacions recurrents == | |||
=== Successió de Fibonacci === | |||
'''Terme general''': <math>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: | |||
# <math>a_{n+k} + c_1a_{n+k-1} + c_2a_{n+k-2} + \ldots + c_ka_n = f(n) \; \forall n \geq 0</math> | |||
# <math>\sum_{n=0}^\infty a_nx^n = \frac{I(x) + x^kF(x)}{1 + c_1x + \ldots + c_kx^k} \text{ ($I(x)$ polinomi de grau $\leq k-1$ que depén de les condicions inicials, $F(x) = \sum_{n \geq 0}f(n)x^n$)}</math> | |||
