Counting

The chart below displays the 4 most common types of counting problems:

  Order Is Important Order Is Not Important
No Repetition Permutation
Electing Class Officers
Choosing r from n can be done in P(n,r) ways, which is n!/(n-r)!.		 Combination
Choosing A Committee
Choosing r from n can be done in C(n,r) ways, which is n!/[(n-r)!r!].
Repetition Is Allowed Permutation with repetition allowed
Character Strings, Words, Bit Strings
Choosing r from n can be done in nr ways.		 Combination with repetition allowed
partitioning an integer r as a sum of n nonnegative integers
Choosing r from n can be done in C(n+r-1,n-1)=C(n+r-1,r) ways.

 

Here is a discussion about combinations with repetition allowed.  The classic problem here is the number of ways one can express an integer r as a sum of n nonnegative integers:  x1 + x2 + x3 + ... + xn = r.    For example, with r = 4 and n = 3, one can write 4=4+0+0; 4=3+1+0; 4=3+0+1; 4=2+2+0; 4=2+1+1; 4=2+0+2; 4=1+3+0; 4=1+2+1; 4=1+1+2; 4=1+0+3; 4=0+4+0; 4=0+3+1; 4=0+2+2; 4=0+1+3; and 4=0+0+4.  There are 15 ways to express 4 in this manner.  The formula given below says the number of ways is C(6,2) which is indeed 15.  The general answer is

C(n+r-1,n-1)=C(n+r-1,r),

which can be proven as follows.  Imagine a bit string of n-1 zeros and r ones.  Think of the zeros are marking the boundaries between piles of ones.  The number of ones in the ith pile is xi.  Thus every such string of zeros and ones gives rise to some way of writing r as x1 + x2 + x3 + ... + xn .  Conversely, every expression  of r as x1 + x2 + x3 + ... + xn can be used to design of string of zeros and ones with xi ones in the ith pile defined with zeros as boundary points.  So the problem of counting the expressions x1 + x2 + x3 + ... + xn = r is exactly the same problem as counting the bit strings that consist of n-1 zeros and r ones.  The number of such strings is much easier to explain:  out of the n+r-1 bit string locations, choose n-1 places to put the zeros and put ones in the remaining places.  Choosing n-1 places out of n+r-1 is like choosing a committee (we only care what places are chosen, not which one was picked first).  The number of ways to do this is C(n+r-1,n-1) [which is the same as C(n+r-1,r)].