Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Okay, it took some processing power, but I totally got it. Thank you very much! –  Garth Marenghi Aug 4 '11 at 12:32
    
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$. –  André Nicolas Aug 4 '11 at 13:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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