What is the combinatorial interpretation of the product of binomial coefficients?

Question

Full disclosure: This question is relating to a homework question. It's not a homework question itself, but rather a clarifying question to help myself get a handle on the actual question.

Suppose I had three sets $X$, $Y$, and $Z$ with cardinalities $|X| = x$, $|Y| = y$, and $|Z| = z$, with $z \leq y \leq x$

I know that $x \choose y$ is the number of ways of selecting $y$ elements from $X$.

However, I'm unclear of the combinatorial interpretation of the following:

$${x \choose y} {y \choose z}$$

So my question is: in general, is there an intuitive interpretation for the product of the number of choices?

Answer 1

A possible interpretation is pairing sets $X$ and $Y$ with no elements of $Y$ left so that would require selecting $y$ elements from $X$ or $\displaystyle \binom xy$, then making triplets with no elemts of $Z$ left that would require selecting $z$ pairs from these $y$ pairs or $\displaystyle \binom yz$.

Answer 2

The answer to your question is affirmative: Yes, there is an intuitive interpretation for the number of choices.

We know at least two interpretations of the binomial coefficient $\binom{n}{k}$ which are useful for combinatorial proofs. These are

• Set theoretical view: $\binom{n}{k}$ as number of $k$-element subsets of an $n$-element set

• Geometrical view: $\binom{n}{k}$ as number of lattice pathes of length $n$ containing $k$ horizontal $(1,0)$-steps and $n-k$ vertical $(0,1)$-steps

The geometrical view is valid because there are $\binom{n}{k}$ choices to select $k$ steps in horizontal direction leaving the remaining $n-k$ steps for the vertical direction.

Let's apply the second approach to

\begin{align*} \binom{x}{y}\binom{y}{z}\qquad z \leq y \leq x\tag{1} \end{align*}

When looking at $\binom{y}{z}$ you may think of all paths of length $y$ starting at $A=(0,0)$ and ending in $B=(z,y-z)$ thereby containing exactly $z$ horizontal $(1,0)$-steps and $y-z$ vertical $(0,1)$-steps. All these paths are enclosed within a rectangle of length $z$ and height $y-z$.

Similarly we consider $\binom{x}{y}$ as the number of lattice paths of length $x$ containing $y$ $(1,0)$-steps and $x-y$ $(0,1)$-steps. But here we let all these paths start in $B=(z,y-z)$ and so they end up in $C=(z+y,x-z)$.

We observe following

Combinatorial interpretation of $$\binom{x}{y}\binom{y}{z}$$

This is the number of lattice paths of length $x+y$ starting in $A=(0,0)$ ending up in $C=(z+y,x-z)$ and passing through the point $B=(z,y-z)$.

The paths contain only horizontal $(1,0)$-steps and vertical $(0,1)$-steps.