0
$\begingroup$

I am currently reading Combinatorics 2nd ed. by R. Merris. I have a hard time getting what the author is trying to say on page 11, paragraph 1.2.2; theorem for Pascal's relation.

It says:

if 1 <= r <= n, then C(n + 1, r) = C(n, r - 1) + C(n, r).

Pascal’s relation implies, e.g., that C(6, 3) = C(5, 2) + C(5, 3) = 20.

Proof. Consider the (n + 1)-element set {x1, x2, xn, y}. Its r-element subsets can be partitioned into two families, those that contain y and those that do not. To count the subsets that contain y, simply observe that the remaining r - 1 elements can be chosen from {x1, x2, xn} in C(n, r - 1) ways. The r-element subsets that do not contain y are precisely the r-element subsets of {x1, x2, xn}, of which there are C(n, r).

In the book it counts the number of ways a subset of 2 numbers can be selected from a set of 5 numbers. There were 10 ways to do this and the author showed this by writing down all the combinations. But I can't figure out how C(6, 3) = C(5, 2) + C(5, 3) is equal to 20. How exactly does it work?

Also, why is 1 added to n in C(n + 1, r)? And why is there a y in the set?

Because the only way to choose an n-element subset from S is to choose all of its elements, C(n, n) = 1. Having n single elements, S has n single-element subsets, i.e., C(n, 1) = n. For essentially the same reason, C(n, n - 1) = n.

How come C(n, 1) is equal to n? Does the writer mean with the 1 the number of ways to choose?

1 Answers 1

1

Instead of $x$'s and $y$'s, let's try green and red balls.

$C(n,r)$ is the number of ways to choose $r$ things from a collection of $n$ items where the order of the things chosen does not matter.

Now consider a collection of green balls numbered from $1$ to $n$ and $1$ red ball. By definition, there are $C(n+1,r)$ ways to choose $r$ balls from the collection of $n+1$. Each choice can be separated into two cases: those with the red ball, and those without.

Let us count the choices with the red ball. Other than the red ball, there are $n$ green balls from which we wish to choose $r-1$. There are $C(n,r-1)$ ways to make this choice.

Next, let us count the choices without the red ball. There are still $n$ green balls from which we wish to choose $r$. There are $C(n,r)$ ways to make this choice.

Totalling the choices from these two cases, we get that the number of ways to choose $r$ balls from the collection of $n+1$ is $C(n+1,r)=C(n,r-1)+C(n,r)$.

How come $C(n,1)$ is equal to $n$?

Given a collection of balls numbered from $1$ to $n$, there are $n$ ways to choose a single ball from the collection. Applying the definition, $C(n,1) = n$.

  • 0
    Good explanation. Interesting how a simple idea can get so buried in notation that its basic simplicity is hidden. Actually, I prefer $n+1$ people, one of whom is Alice. And it is best to first have $9$ people, and choose a committee of $4$.2011-08-04