Counting: Permutations, Combinations and Principles
" without listing. How many passwords of a given form exist, how many ways can tasks be assigned to processors, how many paths cross a grid, how many binary strings avoid a pattern?
Engineering Mathematics · topic
Counting, recurrence relations and generating functions
Sum and product rules, permutations and combinations with and without repetition, distribution models, pigeonhole; inclusion-exclusion, derangements, Catalan and Stirling numbers; linear recurrences, homogeneous and non-homogeneous solution forms; ordinary generating functions and coefficient extraction.
Study this topic
Recurrence Relations
A recurrence relation defines each term of a sequence from earlier terms: a_n = a_n-1 + a_n-2, T(n) = 2T(n/2) + n.
Generating Functions
A generating function packs an entire sequence a_0, a_1, a_2, ... into one power series. Algebra on the series (adding, multiplying, shifting, differentiating) then corresponds to combinatorial operations on the sequence.") and to solve recurrence relations.
Counting, recurrence relations and generating functions cheat sheets
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.