Primeros años de universidadDiscrete MathematicsPlanificado
Recurrences and generating functions
Recurrence relations such as the Fibonacci recurrence, solving linear recurrences, ordinary generating functions and asymptotic notation.
math.discrete.recurrences-generating-functions
La lección de este tema todavía no se ha escrito. El esquema siguiente forma parte del mapa del plan de estudios y no ha sido revisado.
Se basa en
Requisitos previos obligatorios, hasta el fondo: 28
Aprenderás a
- Solve linear recurrences with constant coefficients using characteristic polynomials.
- Use generating functions to solve recurrences and counting problems.
- Compare growth rates using O, Ω and Θ notation.
Definición
- The ordinary generating function of a sequence (aₙ) is the formal power series Σ aₙxⁿ.
- f(n) = O(g(n)) means |f(n)| ≤ C|g(n)| for some constant C and all sufficiently large n.
Teorema
- Binet's formula: with F₀ = 0 and F₁ = 1, Fₙ = (φⁿ − ψⁿ)/√5 where φ = (1 + √5)/2 and ψ = (1 − √5)/2.
- The Catalan numbers C(2n, n)/(n + 1) count, among many other things, balanced sequences of n pairs of brackets.
Errores frecuentes
- Thinking formal power series must converge to be useful.
- Reading big-O as an exact count rather than an upper bound up to a constant.
Conduce a
Descubrimientos opcionales
- Algorithms, correctness and efficiency Recurrences describe the running time of recursive algorithms; mergesort satisfies T(n) = 2T(n/2) + O(n), so T(n) = O(n log n).
Lecturas complementarias
- Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics (1989)
- Herbert S. Wilf, generatingfunctionology (1990)