Four-Letter CombinationsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/