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