Concept

Generating function

A series whose coefficients are the terms of a counting sequence. Multiplying two of them convolves the coefficients, so combining independent choices becomes multiplication and a recursion becomes an equation that can be solved.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

Also named here as partition — the same set of essays touches all of them, so they are one junction rather than several.

The partition 5 + 4 + 2 + 1 and its conjugate. A row of dots for each part, and the same dots read down the columns instead.

A diagram turned on its side

Write a partition as rows of dots, then read the columns instead. Every theorem in this essay is that one move, and the move proves things that no formula suggests.

number · partitions

A product of 3 polynomials, and what its coefficients count. The coefficients of a product of small polynomials, with the combinations of choices that reach one marked total written out beneath it.

A polynomial that counts

Hang a counting sequence on the powers of a variable and the two ways of combining choices — this and that, this or that — become multiplication and addition, so a recursion turns into an equation and the equation can be solved.

discrete · generating functions

Named alongside it

The objects these essays reach for when they reach for this one.

Counting two ways Partition Bijection Binomial coefficient Catalan numbers Conjugate partition Convolution Durfee square Ferrers diagram Formal power series Involution Recurrence relation

All concepts