1
$\begingroup$

How many 3 letter words can be formed using the letters of the word “TESTBOOK”? I'm clueless to solve this question using generating function, can anyone please help me or at least provide some hint.

$\endgroup$
  • 1
    $\begingroup$ Well, as there are only three letters you can have at most one double (there are no available triples). So split into two types: those with a double and those without. $\endgroup$ – lulu Jan 14 '17 at 15:12
  • $\begingroup$ Thanks for reply. Can you show me how to use generating functions here? $\endgroup$ – Mr.Sigma. Jan 14 '17 at 15:14
  • $\begingroup$ And using your approach, getting 138. Answer given is 150 $\endgroup$ – Mr.Sigma. Jan 14 '17 at 15:19
  • 2
    $\begingroup$ By my method: with double, pattern is $XXY$ ...two choices for $X$, then five for $Y$ so $10$, then three places to put the $Y$ so $30$. without double is $\binom 63\times 3! =20\times 6=120$. $\endgroup$ – lulu Jan 14 '17 at 15:24
  • 1
    $\begingroup$ Generating functions seem like a bad way to approach this...they do better when order isn't important. Not immediately seeing a way which is easier than writing out all the cases. $\endgroup$ – lulu Jan 14 '17 at 15:29
3
$\begingroup$

The generating function is $f(z)=\left(1+z+\frac{z^2}{2!}\right)^2\cdot (1+z)^4$

The first two factors represent $t$ and $o$. The other four factors represent $e,x,b,k$

If you expand it you get:

$f(z)=1+\frac{6}{1!}z+\frac{32}{2!}z^2+\frac{150}{3!}z^3+\frac{606}{4!}z^4+...$

There can be formed $6$ words with $1$ letter. $32$ words with $2$ letters. And $150$ words with $3$ letters.

$\endgroup$
  • $\begingroup$ Wonderful. Can you please tell me how 150? Shouldn't it be 150/3! ? $\endgroup$ – Mr.Sigma. Jan 14 '17 at 16:24
  • 1
    $\begingroup$ No, you use the exponential generating function: $f(z)=\sum_{i=0}^{\infty} a_i\cdot \frac{z^i}{i!}=a_0+a_1\cdot \frac{z}{1!}+a_2\cdot \frac{z^2}{2!}+a_3\cdot \frac{z^3}{3!}+\ldots$. The coefficient $a_3=150$. $\endgroup$ – callculus Jan 14 '17 at 18:23

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.