O'Reilly logo

Combinatorics by Peter J. Cameron

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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)

image

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.

Start Free Trial

No credit card required