2
$\begingroup$

I'm having issues with my logic on this problem:

How many ways are there to form a list of three letters from the letters in the word COMBINATORICS if the letters cannot be used more often than they appear in COMBINATORICS?

I'm trying to think of this as a set with 13 elements (2 Cs, 2 Os, 2 Ms, etc). Thus, 13*12*11 would give us 1716 possibilities but apparently that isn't correct.

Any help or clarifications would be greatly appreciated.

$\endgroup$
2
  • $\begingroup$ Think of the fact that , e.g., for a letter with 2 I's, exchanging them will not give you a new word. $\endgroup$ – DBFdalwayse Oct 2 '13 at 2:40
  • $\begingroup$ So, the template could be RRL and LRR where R is a repeated letter and L is a normal letter... 6*1*11 = 66*2 = 132 So 1716 - 132 would give us 1452 $\endgroup$ – Daniel Cazares Oct 2 '13 at 2:54
1
$\begingroup$

A general method for solving this kind of problem uses exponential generating functions. Let $$ \begin{aligned} G(x,C,O,I,M,\ldots)=&\left(1+\frac{Cx}{1!}+\frac{C^2x^2}{2!}\right)\left(1+\frac{Ox}{1!}+\frac{O^2x^2}{2!}\right)\left(1+\frac{Ix}{1!}+\frac{I^2x^2}{2!}\right)\left(1+\frac{Mx}{1!}\right)\\ &\times\left(1+\frac{Bx}{1!}\right)\left(1+\frac{Nx}{1!}\right)\left(1+\frac{Ax}{1!}\right)\left(1+\frac{Tx}{1!}\right)\left(1+\frac{Rx}{1!}\right)\left(1+\frac{Sx}{1!}\right). \end{aligned} $$ The variables $C,$ $O,$ $I,$ $M,$ and so on, are there just to indicate which factor counts which letter, and may all be set equal to $1.$ If we do this, we get $$ G(x):=G(x,1,1,1,1,\ldots)=\left(1+\frac{x}{1!}+\frac{x^2}{2!}\right)^3\left(1+\frac{x}{1!}\right)^7 $$ The coefficient of $x^3$, multiplied by $3!,$ will be the desired number of arrangements.

We get $$ \begin{aligned} G(x)&=\left((1+x)^3+\binom{3}{1}\frac{x^2}{2!}(1+x)^2+\binom{3}{2}\left(\frac{x^2}{2!}\right)^2 (1+x)+\binom{3}{3}\left(\frac{x^2}{2!}\right)^3\right)\,\left(1+x\right)^7\\ &=(1+x)^{10}+\binom{3}{1}\frac{x^2}{2!}(1+x)^9+\ldots. \end{aligned} $$ The coefficient of $x^3$ in this expression is $\binom{10}{3}+\binom{3}{1}\frac{1}{2!}\binom{9}{1}.$ Multiplying by $3!$ gives $_{10}P_3+3\cdot\binom{3}{1}\binom{9}{1}.$

$\endgroup$
3
  • $\begingroup$ You're a saint. Thanks for introducing this to me! $\endgroup$ – Daniel Cazares Oct 2 '13 at 19:32
  • $\begingroup$ What are you referring to when you say the coefficient of x^3? $\endgroup$ – Daniel Cazares Oct 2 '13 at 19:39
  • 1
    $\begingroup$ In this problem $G(x)$ is a polynomial. By the coefficient of $x^3,$ I mean the coefficient of $x^3$ in the polynomial when fully expanded. Note that in general a generating function may be an infinite series, but the same principle applies. $\endgroup$ – user96124 Oct 2 '13 at 22:58
1
$\begingroup$

You need to take into account the multiplicity of the letters; the answer is given by the multinomial coefficients:

http://mathworld.wolfram.com/MultinomialCoefficient.html

In our case for the word combinatorics is given by:

$ \frac{13!}{2!2!2!}$

If you want the number of 3-letter words, then you can partition this collection into:

i) Words with non-repeated letters.

ii)Words with repeat letters.

For i), there are $10P3$ ; "10 permute 3" ways; just select any 3 out of the 10 different letters in any order.

For ii) , you can choose the repeated letter in 3 different ways {$C,O,I$} , and then, for

each choice, there are 10 choices for the remaining letters--any non-repeat letter--and there are 3 ways of arranging the word; 3 places where you can put the non-repeat.

$\endgroup$
1
  • $\begingroup$ Oh, sorry, I thought it was the number of arrangements/permutations. Let me redo. $\endgroup$ – DBFdalwayse Oct 2 '13 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.