0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If $x\le y\le z$ then both of those coefficients are $0$ $\endgroup$ – Adam Hughes Sep 19 '14 at 1:50
  • $\begingroup$ You're right, sorry; I'm updating my question now $\endgroup$ – Jason Baker Sep 19 '14 at 1:51
  • 4
    $\begingroup$ 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$? $\endgroup$ – Semiclassical Sep 19 '14 at 1:54
  • $\begingroup$ @Semiclassical That makes sense; thanks for the confirmation $\endgroup$ – Jason Baker Sep 19 '14 at 1:57
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.