Combinatorial Families

Question

I arrived at this video on combinatorial families in a playlist, but I don't really understand the main idea. The explanation in the first 90 seconds isn't very clear, and then it moves on to list various identities. The only other resource I can find on the subject is a mention in passing on Wikipedia.

Is there a difference between the combinatorial family corresponding to a generating function, as outlined in the video, and the sequence which is generated by the generating function, or are these two things synonymous?

Answer 1

From the point of view of a generating function, a combinatorial family "is" just a sequence $\langle a_0, a_1, a_2, \dots \rangle$ of nonnegative integers. Generating functions are just dumb mathematical objects who don't really understand human intuitions.

From the point of view of human problem-solvers, a combinatorial family $\mathcal A$ is a set (or family) of objects counted by this sequence. Each object has an associated "length" or "weight" or whatever you want to call it; the weights are nonnegative integers. For the combinatorial family $\mathcal A$ to be counted by the sequence $\langle a_0, a_1, a_2, \dots \rangle$, we would like there to be exactly $a_i$ objects in $\mathcal A$ with "weight" or "length" $i$.

Some examples:

• Consider the combinatorial family of all finite binary strings: finite sequences of zeroes and ones, like $11010110$ or $00011$ or even the empty string. Here, "length" is number of digits. This combinatorial family is counted by the sequence $\langle 1, 2, 4, 8, \dots \rangle$ which has generating function $A(x) = \frac1{1-2x}$.
• Consider the combinatorial family in which the length-$n$ objects are tilings of $1\times n$ rectangles with $1 \times 1$ and $1 \times 2$ tiles. This combinatorial family is counted by the sequence $\langle 1, 1, 2, 3, 5, 8, \dots\rangle$ which has generating function $B(x) = \frac1{1-x-x^2}$.
• Consider the combinatorial family of correctly matched parenthetical expressions, such as $(())()$ or $((((()()()))))$. Here, "length" is number of $($'s. This combinatorial family is counted by the sequence $\langle 1, 1, 2, 5, 14, \dots\rangle$ which has generating function $C(x) = \frac{1-\sqrt{1-4 x}}{2 x}$.

The point of distinguishing between the combinatorial family, the sequence, and the generating function is that nice arithmetical operations on generating functions correspond to weird arithmetical operations on sequences which correspond to nice combinatorial operations on combinatorial families.

For example, as mentioned in the video, the product $A(x) \cdot B(x) = C(x)$ corresponds to a convolution of sequences: $a_n b_0 + a_{n-1}b_1 + \dots + a_0 b_n = c_n$. This corresponds to a Cartesian product of combinatorial families: $\mathcal C = \mathcal A \times \mathcal B$, with the "length" or "weight" of an ordered pair $(a,b) \in \mathcal C$ corresponding to the sum of the $\mathcal A$-weight of $a$ and the $\mathcal B$-weight of $b$.