Counting Techniques
This page presents a fuller discussion of counting techniques which were
employed in calculating combinations for the
binomial distribution. A reasonable sequential
approach considers the following [all of which are relevant to "without
replacement" problems]:
The basic question of how many ways one can arrange n distinct objects (e.g.,
line 5 people up, place seven books on a shelf) is answered with the factorial.
If there are 5 people, any of the five can be at the head of the line, which
leaves 4 for the second position (no matter who is at the head of the line),
and three will remain for the third position (no matter who the first two are).
This reasoning provided that there are 5x4x3x2x1=120 ways to arrange five
people. The definition of n factorial (denoted n!) is n!=n(n-1)(n-2) ... (1).
By definition, 0!=1. The factorial is only defined for nonnegative integers.
The factorial embodies/represents/manifests order.
Often one is only interested in ordering a few items rather than all the
objects in a set. For example, if one wants to choose a president,
vice-president, and secretary-treasurer from a class of 10 students, there are
10 choices for the president, which leaves nine for the vice-president, and then
eight for the secretary-treasurer; hence there are 10x9x8=720 different slates
of class officers. This truncated factorial 10x9x8=(10!)/(7!). This is the
definition of permutations, in one of many notations, P(n,r)=(n!)/(n-r!), which
is read as "n permute r". Here the factorial embodies order: it orders all the
10 people in the numerator, then removes the order among the seven individuals
who do not hold office in the denominator. Note that n and r are both
nonnegative, and n is greater than or equal to r.
Sometimes one does not care about order among items which are chosen, such as
when has eight shirts, and throws three into his duffel bag for a weekend
trip. Since P(8,3)=336 is the number of ordered sets of three shirts and there
are 3!=6 ways to order each set of three shirts, there are 336/6=56 unordered
sets of 3 shirts. This provides the definition for combinations:
C(n,r)=(n!)/((r!)((n-r)!)) (C(n,r) is read " n choose r"), in the shirt example
8!/((3!)(5!))=56 (the
factorials in the denominator remove order among the shirts which are taken and
the shirts which are left behind. This symmetry of chosen and unchosen is also
manifest in the use of combinations as binomial
coefficients.
There are many ways to extend the above counting techniques. For example, one
can determine the number of arrangements of letters in a word. The number of
arrangements of the letters in IOWA is 4!=24, since all the letters are
distinct. The number of arrangements of the letters in OHIO is 4!/2=12 since
4! would distinguish between the initial and terminal 'O', providing two
arrangements for every visually distinguishable order. The number of
arrangements of MISSISSIPPI is (11!)/((1!)(4!)(4!)(2!))=34650; 11! orders 11
distinct objects in the numerator, and the denominatior removes order among the
M, the the I's, the S's, and the P's. Note that 4!=(4!)/((1!)(1!)(1!)(1!)) and
12=(4!)/((2!)(1!)(1!)).
return to index
Questions?