from the remaining n – 1 students. If John is not to be
on the committee, then one must select k students from
the pool of n – 1 students that excludes John.)
3.
(There are
possible committees of
any size. But this number can also be computed by
deciding, student by student, whether or not to put that
student in the committee. As there are two possibilities
for each student, in or out, there are 2
n possible committees. These counts must be the same.)
4.
(Suppose, in the committee, one student is to be
selected as chair. In a committee of size k there are k
possible choices for chair. Thus
counts the
total number of committees possible, of any size, with
one student selected as chair. But this quantity can also
be computed by selecting some student to be chair
first—there are n choices for this—and then deciding,
student by student, among the remaining n – 1 students
whether that student should be on the committee. This
yields n2
n–1 possibilities.)
Property 1 explains why Pascal’s triangle is symmetric. Property 2 shows that each entry in Pascal’s triangle is the sum of the two entries above it, and
property 3 shows that the sum of all the entries in any
row of Pascal’s triangle is a power of two.
In 1778 LEONHARD EULER used the notation
for the combinatorial coefficients, which, three years
later, he modified to
. In the 19th century, mathematicians started following Euler’s original notation,
dropping the VINCULUM for the purposes of easing
typesetting. Many textbooks today use the notation
n C k , or C
n
k , or even C(n,k), for the combinatorial
coefficient
.
Generalized Coefficients
The generalized combinatorial coefficient
,
where k 1 ,k 2 ,…,k r are nonnegative integers summing to
n, is defined to be the number of ways one can select,
from n items, k 1 objects to go into one container, k 2
objects to go into a second container, and so forth, up
to k r objects to go into an rth container. (Notice that
is the ordinary combinatorial coefficient.)
Mimicking the argument presented above, note that
one can arrange n items in a row by first selecting
which k 1 items are to go into the first part of the row
and ordering them, which k 2 items are to go in the
next portion of the row and ordering them, and so on.
This shows that
, yielding
the formula:
Generalized combinatorial coefficients show, for
example, that there are
ways to rearrange the letters CHEESES: Of the seven
slots for letters, one must choose which slot is assigned
for the letter C, which one for the letter H, which three
for the letter E, and which two for letter S.
The generalized combinatorial coefficients also
appear in generalizations to the BINOMIAL THEOREM.
For example, we have the trinomial theorem:
where the sum is taken over all triples k 1 ,k 2 ,k 3 that
sum to n. The proof is analogous to that of the ordinary binomial theorem.
Multi-Choosing
The quantity
, read as “n multi-choose k,” counts
the number of ways to select k objects from a collection
4
2
(
)
x y z
n
k k k
x y z
n
k kk
i
+ +
=
∑
1 2 3
2
3
7
1 1 3 2
7
1 1 3 2
420
=
=
!
! ! ! !
n
k k
k
n
k k
k
r
r
1 2
1 2
K
K
=
!
! !
!
n
n
k k
k
k k
k
r
r
!
! !
!
=
1 2
1 2
K
K
n
k n k
−
n
k k
k r
1 2 K
n
k
n
k
n
k
k
n
k
k
n
=
∑
0
k
n
k
n
n
n
n
n
n
n
n
k
n
=
+
+
+ +
=
−
=
∑
1
2
2
3
3
2
1
0
L
n
n
n
n
0
1
+
+ +
L
n
k
n
n
n
n
n
k
n
n
=
+
+
+ +
=
=
∑
0
1
2
2
0
L
combination 81
on the committee, then one must select k students from
the pool of n – 1 students that excludes John.)
3.
(There are
possible committees of
any size. But this number can also be computed by
deciding, student by student, whether or not to put that
student in the committee. As there are two possibilities
for each student, in or out, there are 2
n possible committees. These counts must be the same.)
4.
(Suppose, in the committee, one student is to be
selected as chair. In a committee of size k there are k
possible choices for chair. Thus
counts the
total number of committees possible, of any size, with
one student selected as chair. But this quantity can also
be computed by selecting some student to be chair
first—there are n choices for this—and then deciding,
student by student, among the remaining n – 1 students
whether that student should be on the committee. This
yields n2
n–1 possibilities.)
Property 1 explains why Pascal’s triangle is symmetric. Property 2 shows that each entry in Pascal’s triangle is the sum of the two entries above it, and
property 3 shows that the sum of all the entries in any
row of Pascal’s triangle is a power of two.
In 1778 LEONHARD EULER used the notation
for the combinatorial coefficients, which, three years
later, he modified to
. In the 19th century, mathematicians started following Euler’s original notation,
dropping the VINCULUM for the purposes of easing
typesetting. Many textbooks today use the notation
n C k , or C
n
k , or even C(n,k), for the combinatorial
coefficient
.
Generalized Coefficients
The generalized combinatorial coefficient
,
where k 1 ,k 2 ,…,k r are nonnegative integers summing to
n, is defined to be the number of ways one can select,
from n items, k 1 objects to go into one container, k 2
objects to go into a second container, and so forth, up
to k r objects to go into an rth container. (Notice that
is the ordinary combinatorial coefficient.)
Mimicking the argument presented above, note that
one can arrange n items in a row by first selecting
which k 1 items are to go into the first part of the row
and ordering them, which k 2 items are to go in the
next portion of the row and ordering them, and so on.
This shows that
, yielding
the formula:
Generalized combinatorial coefficients show, for
example, that there are
ways to rearrange the letters CHEESES: Of the seven
slots for letters, one must choose which slot is assigned
for the letter C, which one for the letter H, which three
for the letter E, and which two for letter S.
The generalized combinatorial coefficients also
appear in generalizations to the BINOMIAL THEOREM.
For example, we have the trinomial theorem:
where the sum is taken over all triples k 1 ,k 2 ,k 3 that
sum to n. The proof is analogous to that of the ordinary binomial theorem.
Multi-Choosing
The quantity
, read as “n multi-choose k,” counts
the number of ways to select k objects from a collection
4
2
(
)
x y z
n
k k k
x y z
n
k kk
i
+ +
=
∑
1 2 3
2
3
7
1 1 3 2
7
1 1 3 2
420
=
=
!
! ! ! !
n
k k
k
n
k k
k
r
r
1 2
1 2
K
K
=
!
! !
!
n
n
k k
k
k k
k
r
r
!
! !
!
=
1 2
1 2
K
K
n
k n k
−
n
k k
k r
1 2 K
n
k
n
k
n
k
k
n
k
k
n
=
∑
0
k
n
k
n
n
n
n
n
n
n
n
k
n
=
+
+
+ +
=
−
=
∑
1
2
2
3
3
2
1
0
L
n
n
n
n
0
1
+
+ +
L
n
k
n
n
n
n
n
k
n
n
=
+
+
+ +
=
=
∑
0
1
2
2
0
L
combination 81