2
$\begingroup$

How many distinct three-letter sequences with at least one $T$ can be formed by using three of the six letters of $TARGET$? One such sequence is $T-R-T$. [MathCounts 2005 National Countdown]

The problem given is easy, because the word given is small enough for casework. (One $T$ implies there are $3*4*3=36$ words. Two implies there are $3*4=12$).

However, how does this generalize to $n$ given characters and $m<n$ letter long distinct words? If $n=m$, there is the standard technique of dividing by the number of repeated letters factorial, but for a long word such as $AAABCCDEEEFFG$, I don't know how to effectively compute all possible $7$ letters words.

(All I need is this, as generalizing the "at least one $T$'s" part is just subtracting the words that can be made with zero $T$'s)

$\endgroup$
1
$\begingroup$

There is a generating function approach for this.

Classify letters in AAABCCDEEEFFG according to frequency of occurrence.

Three occur once [B, D, G], two occur twice [C, F], and two occur thrice [A, E].

Find the coefficent of $x^7$ in $7!\cdot(1+x)^3\cdot(1+x + x^2/2!)^2\cdot (1+x+x^2/2!+x^3/3!)^2$

PS

Re your query, look here

$\endgroup$
4
  • $\begingroup$ The coefficient from Wolfram is 727/18 $\endgroup$ – Nicholas Pipitone Jul 26 '15 at 19:08
  • $\begingroup$ Sorry. 7! multiplier got omitted, has been inserted. Answer will be 203,560. $\endgroup$ – true blue anil Jul 26 '15 at 19:22
  • $\begingroup$ Can you provide a proof of this? I do not understand why this works. $\endgroup$ – Nicholas Pipitone Jul 26 '15 at 20:00
  • $\begingroup$ See link given in PS $\endgroup$ – true blue anil Jul 27 '15 at 3:17

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.