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?