Concept

Convolution

The sequence whose n-th term sums the products of terms of two sequences whose indices add to n. It is what a product of generating functions computes, which is why a recurrence involving a split becomes an algebraic equation.

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

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

The equation the objects satisfy. A diagram of the decomposition C = 1 + xC², with a table of the first several coefficients computed two ways: by the convolution the equation prescribes, and from the closed form.

The equation a sequence satisfies

Write the whole sequence as the coefficients of one series, and the recursion becomes an equation with a square in it. Solving the equation by the ordinary quadratic formula produces the closed form, the growth rate and the correction term, none of which the recursion offers.

discrete · Catalan numbers

Named alongside it

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

Binomial coefficient Catalan numbers Generating function Asymptotics Counting-two ways Formal power series Partition Power series Recurrence relation Recursion Singularity

All concepts