Recurrences and generating functions

इस पर आधारित

28 अनिवार्य पूर्वापेक्षाएँ (बिल्कुल नीचे तक)

आप सीखेंगे

• 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.

परिभाषा

• 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.

प्रमेय

• 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.

आम भ्रांतियाँ

• 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.

आगे ले जाता है

वैकल्पिक खोजें

• 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).

आगे पढ़ने के लिए

• Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics (1989)
• Herbert S. Wilf, generatingfunctionology (1990)