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

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?

• If $x\le y\le z$ then both of those coefficients are $0$ – Adam Hughes Sep 19 '14 at 1:50
• You're right, sorry; I'm updating my question now – Jason Baker Sep 19 '14 at 1:51
• There's two interpretations. 1) How many ways are there to first pick $y$ elements out of $x$, and then pick $z$ elements out of these $y$? 2) How many ways are there to divide $x$ into sets of size $z$, $y-z,$ and $x-y$? – Semiclassical Sep 19 '14 at 1:54
• @Semiclassical That makes sense; thanks for the confirmation – Jason Baker Sep 19 '14 at 1:57

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 on all pathes 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 pathes are enclosed within a rectangle of length $z$ and height $y-z$.

Similarly we consider $\binom{x}{y}$ as the number of lattice pathes of length $x$ containing $y$ $(1,0)$-steps and $x-y$ $(0,1)$-steps. But here we let all these pathes 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 pathes 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 pathes contain only horizontal $(1,0)$-steps and vertical $(0,1)$-steps.

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$.