# Number of distinct permutations given a character set.

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)

## 1 Answer

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

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