## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

4.  Recurrence relations and generating functions

The way begets one; one begets two; two begets three; three begets the myriad creatures.

Lao Tse, Tao Te Ching (ca. 500 BC)

TOPICS: Fibonacci, Catalan and Bell numbers, derangements, [finite fields, sorting, binary trees, ‘Twenty Questions’]

TECHNIQUES: Recurrence relations, solution of linear recurrence relations with constant coefficients, generating functions and their manipulation, [the ring of formal power series]

ALGORITHMS: Computation of Fibonacci numbers, [QUICKSORT]

CROSS-REFERENCES: Derangements (Chapter 5), set partitions (Chapter 3)

A recurrence relation expresses the value of a function ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required