Some Principles of Counting

Definitions. Two sets A and B are said to have the same cardinality if there is a 1 to 1 function from A onto B. If n is a positive integer, then a set A is said to have cardinality n (or have n elements ) if A has the same cardinality as the set B = . A set is finite if it has cardinality n for some positive integer n. If A is a finite set, the notation |A| is used to denote the cardinality of A. Thus if A = {a, b, c, 4, 2}

then |A| = 5.

Suppose X is a finite set you would like to count. Here are seven methods to try.

Brute force. . Make a listing of the members of X and enumerate it.

Use brute force when you are trying to see a counting pattern in order to conjecture a counting formula. Constantly use it to check the accuracy of your solution of a counting problem.

Partition X. If X is partitioned into a collection of pairwise disjoint nonempty subsets , i = 1..n. then

This is a time honored 'divide and conquer' method. There are always ways to bust X into littler subsets which might be more easily counted.

Problem. How many words with n letters start with 'an' or 're'. (A word is a finite sequence of letters from the 26 letter alphabet. Repititions are allowed.)

Solution. did in class.

Overcount and correct : If X is the union of finite nonempty sets A and B, then |X| = |A| + |B| - |A intersect B|

Justification. This counting formula follows from the partition formula above: if A intersect B is empty, then it we have a partition of X into A and B; otherwise we have a partition into 3 sets: A-B, A intersect B, and B-A, so |X| = |A-B| + |A intersect B| + |B-A| = |A| + |B-A| = |A| + |B-A| + |A intersect B| - |A intersect B| = |A| + |B| - |A intersect B|.

Problem (a poker probelm). How many 5 card hands are straight or flush (a straight is 5 in a row, a flush is all 5 of one suit).

Solution. did in class.

Overcount and correct (general case): If X is the union of the sets , i = 1..n, then

Problem. State and justify the formula above for the cases n = 3 and n = 4. Make up poker problems which can be solved using these formulas.

Solution. Chris Rakes will show us this.

Count and multiply. If X is partitioned into m sets, each with n elements, then |X| = n*m.

Problem. A special deck of cards has m suits, each of which has n cards. How many cards in the deck?

Solution. did in class.

Factor X. If X is the cartesian product of two finite sets A and B, then |X| = | A x B | = | A | * | B |. More generally, if X is the cartesian product of n sets , then .

Use this formula when the elements of X can be thought of as sequences of n indecpendent choices.

Problem. Each book of a library of m (distinct) books is to be marked with 1 of n (distinct) colors, including red. How many different ways can this be done. Note: One way would be to mark them all red.

Count the complement. If X is the complement of A in B, then .

This is also called indirect counting .

Problem. Justify this formula using some of the previous formulas.

Solution. Good exam question.

Problem. Toss a coin n times. How many sequences have at least 2 heads?

Solution. did in class.

More Counting problems.

Problem. How many 5 card hands contain at least one 1 card from each suit?

Solution: count the complement by partitioning. The complement is all 5 card hands that are missing a suit. This breaks up into 4 sets with the same number of elements: all hands with no hearts (spades, clubs, diamonds). The number of hands with no hearts is binomial(3*13,5) so the number sought is binomial(52,5) - 4 * binomial(3*13,5).

> binomial(52,5) - 4 * binomial(3*13,5);

I wouldn't want to check this by brute force.

Problem. How many integers beween 1 and 10000 are divisible by neither 2, 3, 5, 7 or 11?

Solution 1 . Count the complement with counting and overcorrecting in the case n = 5.

> n := 10000;

> primes := [2,3,5,7,11];
pp := [seq(seq(primes[i]*primes[i+j],j=1..nops(primes)-i),i=1..nops(primes))];
ppp:=[ seq(seq(seq(primes[i]*primes[i+j]*primes[i+j+k],k=1..nops(primes)-i-j),j=1..nops(primes)-i),i=1..nops(primes))];
prms := convert(primes,`*`);
pppp:= [seq(prms/primes[j],j=1..nops(primes))];

>

Solution 2. Brute force.

> irem(10000,7);

> i := 'i': j := 'j':s := 0 : for i from 1 to n do
if product(irem(i,primes[j]),j=1..nops(primes)) > 0 then s := s+1 fi od:
s;

Same answer. Yahoo!

Problem. How many nonegative integer solutions to the equation ?

Solution: Several people supplied a nice solution to this problem. The idea is to place 27 + 6 pegs in a row and then choose at random 6 pegs. There are binomial(27+6,6) ways to do this. Each choice corresponds uniquely to a solution (x1,x2,x3,x4,x5,x6,x7) to the equations in the following way: say the choice was the 1st, 10th, 11th, 13th, 20th, and 32nd pegs. Then the corresponding solution is x1 = 0 = number of pegs before the 1st one, x2 = 8 = number pegs between the 1st and 10th, etc, yielding the 7 tuple (0,8,0,1,6,11,1). Conversely each solution corresponds to a unique choice of 6 of the 33 pegs.

So the answer is binomial(33,6) = .

Here is a related problem.

Problem. How many positive integer solutions to the equation ?

Solution 1 . We could count the solutions in which at least one of the variables is 0 and subtract that from the answer to the previous problem. Let be th solutions where . Note that for all i. For , let be the solutions where =0. Note that there are binomial (7,2) of these sets and for all . Then the cardinality of the union of the sets A[i] is, by the overcount and correct formula for the case n = 7,

abs(A[1])*`U...U`*abs(A[7]) - sum(abs(A[i,j]), 1 = `i < j <= n`..` `) +

> i := 'i':binomial(33,6)-sum((-1)^(i+1)*binomial(7,i)*binomial(33-i,6-i),i=1..6);

Solution 2. Here is a clever solution. Let y[i] = x[i]-1, and note that the positive solutions to the original equation are nonegative solutions to the equation . By the previous device, this is binomial(20+6,6).

> binomial(20+6,6);

Same answer. Yahoo!

Problem. A function f: A -> A is said to be fixed point free provided for all x in A. If A has n elements, how many functions f: A -> A are fixed point free?

Solution. Count the ones with at least one fixed by overcounting and correcting. Then subtract that from

Here is a function fp. fp(n) is the number of selfmaps of an n-element set which fixed at least on point.

> fp := proc(n)
local i;
sum((-1)^(i+1)*binomial(n,i)*n^(n-i),i=1..n) end;

So for n = 5,

> fp(5);

fpf returns the number of fixed point free selfmaps on an n-element set.

> fpf := n-> n^n - fp(n);

> fpf(5);

Question. Does the proportion of fixed point free selfmaps tend to a limit as n gets large?

> rat := n ->(n^n-fp(n))/n^n;

> for i from 1 to 5 do evalf(rat(1000+10*i)) od;

> evalf(rat(1020));

> seq(evalf(rat(1000+10*i)),i=1..5);

> evalf(rat(1200));

>

Related Problem. A permuation f: A -> A is said to be fixed point free provided for all x in A. If A has n elements, how many permutations f: A -> A are fixed point free?

Problem. N men check their hat at a play. At the end, each man gets a hat back. What's the probability no man gets his own hat back?

Solution. Let fpfperm(n) be the answer to the above related problem. then the answer to this problem is .

Problem. Each book of a library of m (distinct) books is to be marked with 1 of n (distinct) colors, including red. How many different ways can this be done, assuming that each color is used at least once.

Solution. Let l(m,n) be the answer to this problem.