Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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}.$
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.
