Suppose we want to
count the number of r-element subsets
in an n-element set. For example, if
S = {a, b, c, d}, then there are four
3-element subsets of S:
{a, b, c}, {a, b, d}, {a, c, d}, and
{b, c, d}.
Is there a formula
for the general case?
The answer is yes.
An easy way to see this is to first count the number of r-element permutations of the n
elements, which is given by the formula
.
Now each r-element subset has r! distinct r-element permutations, which we have
included in our count P(n, r). How do
we remove the redundant permutations from the count? Let C(n, r) denote the number of r-element
subsets of an n-element set. Since
each of the r-element subsets has r! distinct
permutations, it follows that r! × C(n, r) = P(n, r). Now
divide both sides by r! to obtain the formula
. (2.5)
EXAMPLE
4. If S = {a, b, c, d, e}, then all the three-element subsets of S are listed
as follows:
{a,
b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e},
{a,
d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.
There are 10 such
subsets, and we can verify the number by the calculation
.
The expression C(n, r) is usually said to represent the
number of combinations of n things taken r at a time. With combinations, the order in which the objects
appear is not important. We count only the different sets of objects. The
expression C(n, r) is often read "n choose r."
Notice how C(n, r) crops up in the following binomial
expansion of the expression {x + y)4:
(x + y)4 = x4
+ 4x3y + 6x2y2 + 4xy3 + y4 =
= C(4,0)x4 + C(4,1)x3y + C(4,2)x2y2
+ C(4,3)xy3 + C(4,4)y4
Another useful way
to represent C(n, r) is with the binomial coefficient
symbol:
.
Using this symbol,
we can write the expansion for (x + y)4 as follows:
.
This is an instance
of a well-known formula called the binomial
theorem, which can be written as follows, where n is a natural number:
. (2.6)
The binomial
coefficients for the expansion of (x + y)n can be read from the nth row of Table 6.1.
The table is called Pascal's triangle – after the philosopher and mathematician Blaise Pascal (1623-1662). However, the triangle was known
prior to the time of Pascal in China, India, the Middle East, and Europe.
Notice that any interior element is the sum of the two elements above and to
its left.
Table
2.1 – Pascal's triangle.
|
n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
2 |
1 |
2 |
1 |
|
|
|
|
|
|
|
|
|
3 |
1 |
3 |
3 |
1 |
|
|
|
|
|
|
|
|
4 |
1 |
4 |
6 |
4 |
1 |
|
|
|
|
|
|
|
5 |
1 |
5 |
10 |
10 |
5 |
1 |
|
|
|
|
|
|
6 |
1 |
6 |
15 |
20 |
15 |
6 |
1 |
|
|
|
|
|
7 |
1 |
7 |
21 |
35 |
35 |
21 |
7 |
1 |
|
|
|
|
8 |
1 |
8 |
28 |
56 |
70 |
56 |
28 |
8 |
1 |
|
|
|
9 |
1 |
9 |
36 |
84 |
126 |
126 |
84 |
36 |
9 |
1 |
|
|
10 |
1 |
10 |
45 |
120 |
210 |
252 |
210 |
120 |
45 |
10 |
1 |
But how do we
really know that the following statement is correct?
The element in the nth row and kth column of the triangle is
. (2.7)
Let's continue our
discussion about combinations by counting bags of things rather than sets of
things. Suppose we have the set A = {a,
b, c}. How many three-element bags can we construct from the elements of A?
We can list them as follows:
[a, a, a], [a, a, b], [a, a, c], [a, b, c], [a, b, b],
[a, c, c], [b, b, b], [b, b, c], [b, c, c], [c, c, c].
So
there are 10 three-element bags constructed from the elements of {a, b, c}. Let's see if we can find a
general formula for the number of k-element
bags that can be constructed from an n-element
set. For convenience, we'll assume that the n-element set is A = {1, 2, ..., n}.
Suppose that b = { x1, x2, x3, . . . , xk}
is some k-element bag with elements
chosen from A, where the elements of b
are written so that x1
< x2 < ... < xk.
This allows us to construct the following k-element
set:
B= {x1, x2 + 1, x3 + 2, . . . , xk + (k - 1)}.
The numbers xi + (i - 1) are used to ensure that
the elements of B
are distinct elements in the set C = {1, 2, . . . , n + (k - 1)}. So we've
associated each k-element bag b over A with a k-element subset B of C. Conversely, suppose that {y1, y2, y3, . . . , yk} is
some k-element subset of C, where the
elements are written so that y1 ≤
y2 ≤ ... ≤ yk.
This allows us to construct the k-element
bag
{y1, y2-1, y3-2, . . . , yk-(k-1)},
whose elements come from
the set A. So we've associated each k-element
subset of C
with a k-element bag over A.
Therefore the
number of k-element bags over an n-element set is exactly the same as the
number of k-element subsets of a set with n + (k
- 1) elements. This gives us the following result:
Bag Combinations
The number of k-element bags whose distinct elements are chosen from n n-element
set is given by the following formula, where k and n are positive:
(2.8)
EXAMPLE
5. In how many ways can four coins be selected from a collection of
pennies, nickels, and dimes? Let S = {penny, nickel, dime}. Then we need the
number of four-element bags chosen from S. The answer is

EXAMPLE
6. In how many ways can five people be selected from a collection of
Democrats, Republicans, and Independents? Here we are choosing five-element
bags from a set of three characteristics {Democrat, Republican, Independent). The answer is
