Four-Letter Combinations

Date: 09/06/99 at 19:45:49
From: Harpreet Singh
Subject: Combinations

I have been trying to answer this question by finding a general 
formula but have been unsuccessful. I would appreciate it greatly if 
you could help me.

Question: Find the number of combinations of the letters of each of 
the following words, taken four together: (1) COLLEGE (2) PRINCIPAL.

Answer: Here is what I tried for COLLEGE:

It has 2 L's and 2 E's, so

comb's = no. of 4 letter words with exactly 1 E and 1 L   .........[A]
         + no. of 4 letter words with exactly 2 E's    ............[B]
         + no. of 4 letter words with exactly 2 L's   .............[C]
         + no. of 4 letter words with exactly 2 E's and 2 L's   ...[D]
         + no. of 4 letter words with exactly 1 E and no L   ......[E]
         + no. of 4 letter words with exactly 1 L and no E   ......[F]
         + no. of 4 letter words without E or L   .................[G]

       = [A] + [B] + [C] + [D] + [E] + [F] + [G]

Now  for [A], 2 places are filled by 1 E and 1 L, so 2 places are left 
and 3 letters(c,o,g) are available. So C(3,2) = 3 ways.

For [B], 2 places are filled by 2 E's, so 2 places are left and 4 
letters (c,o,l,g) are available. So C(4,2) = 6 ways.

For [C], similarly 6 ways.

For [D], 1 way.

For [E], 1 place has been filled by 1 E, so 3 places are left and 3 
letters (c,o,g) are left. So C(3,3) = 3 ways.

For [F], similarly 3 ways.

For [G], no places have been filled with E's or L's, so 4 places left 
and 5 letters (c,o,l,e,g) are available. So C(5,4) = 5 ways.

So total = 3 + 6 + 6 + 1 + 3 + 3 + 5 = 27 ways.

Thanks
Harpreet Singh

Date: 09/07/99 at 07:45:05
From: Doctor Anthony
Subject: Re: Combinations

1) COLLEGE: We have 7 letters with 2 L's, 2 E's, 1 C, 1 O, 1 G

The number of combinations of 4 letters will be the coefficient of x^4 
in the expansion of (1+x+x^2)^2.(1+x)^3

     = 1 + 5x + 12x^2 + 18x^3 + 18x^4 + ...

So there are 18 combinations of 4 letters.

2) PRINCIPAL: 9 letters with 2 P's, 2 I's, 1 R, 1 N, 1 C, 1 A, 1 L

The number of combinations of 4 letters will be coefficient of x^4 in 
the expansion of (1+x+x^2)^2.(1+x)^5

     = 1 + 7x + 23x^2 + 47x^3 + 66x^4 + ...

and so there are  66 combinations of 4 letters. 

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   

Date: 09/07/99 at 13:06:21
From: Harpreet Singh
Subject: Combinations: Explanation of your great answer

Thanks a lot for the quick response. It would be even more helpful if 
you could tell the concept behind taking the coefficient of x^4 in 
(1+x+x^2)^2.(1+x)^3 for the word COLLEGE.

Thanks a lot
Harpreet Singh

Date: 09/07/99 at 15:28:31
From: Doctor Anthony
Subject: Re: Combinations: Explanation of your great answer

The expression (1+x+x^2)^2.(1+x)^3 is called a generating function. 
These functions provide the best way of enumerating the number of ways 
that items can be chosen from a list of items, particularly where some 
items are repeated. For example, the letter E can be chosen 0, 1, 2 
times, so we include the bracket 1+x+x^2 to cover this set of 
possibilities. Similarly L occurs twice so could be chosen 0, 1, 2 
times, giving a second bracket (1+x+x^2). Then there are 3 letters, 
each of which could be chosen 0 or 1 times. These give rise to the 
factors (1+x)^3. The number of ways of getting a total of 4 x's will 
be the coefficient of x^4 in the expansion of the generating function. 
In this way a purely algebraic method can be applied to the 
combinatorial problem. With more difficult problems, the use of a 
mathematics package like Mathcad or Mathematica allows these problems 
to be solved in a few seconds.

Most textbooks in combinatorics will include chapters on generating 
functions and I would recommend that you have a look at such a book if 
one is available.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/