4

How many distinct strings of length 4 can be generated with $c,b,b,a,a,d$

Through a script I know that there are 102 such possibilities.

My Attempt

Case 1: using only one 'b' and one 'a'. This can happen in 4! number of strings.

Case 2: using two 'a' and no 'b'. 12

Case 3: using two 'b' and no 'a'. 12

Case 4: Using two 'a' and one 'b'. 12*2

Case 5: Using two 'b' and one 'a'. 12*2

Case 6: Using two 'a' and two 'b' only. 6

Adding numbers from all the cases I get 102 which actually complies with the script findings.

Question

Is there any better way to do this, a formula?

Sohail
  • 145

2 Answers2

2

The coefficient of $x^n/n!$ in the product $$(1+x)^2(1+x+x^2/2!)^2 = 1+4x+ 7x^2+ 7x^3+ \frac{17}{4}x^4+\frac{3}{2}x^5+\frac14 x^6$$ counts the number of strings of length $n$ you can make with that multiset of letters. The coefficient of $x^4/4!$ is $4! (17/4)=102.$

For a more general set of letters you get a factor of $(1+x+x^2/2!+\cdots+ x^k/k!)$ for a letter which is allowed to appear up to $k$ times.

Tad
  • 6,679
  • coefficient of $x^4$ in $4!(1+x)^2(1+x+x^2/2!)^2$ – true blue anil Oct 15 '15 at 13:24
  • @trueblueanil exactly. (You say "tomato", I say "tomahto"...) – Tad Oct 15 '15 at 17:29
  • Just given as a variant :-) – true blue anil Oct 15 '15 at 17:51
  • Hello, I know years passed but if possible, can you help me understand how you constrcuted that formula. I couldn't figure out. [well years didn't pass it seems : ) ] – xcvbnm Nov 19 '15 at 21:11
  • 1
    The formula is a straightforward application of exponential generating functions. I was going to leave it at that, but it's not so easy to find a good reference. Try this one (section 2.5): http://www.pitt.edu/~kaveh/Chap2-MATH1050.pdf – Tad Nov 19 '15 at 23:49
  • Thank you very much. I will study it. (and for further reference; link is accessible with www2 http://www2.pitt.edu/~kaveh/Chap2-MATH1050.pdf ) – xcvbnm Nov 20 '15 at 01:04
1

You can do it using only three cases: The string $4$ has either two pairs of repeated letters (i.e., is a permutation of $aabb$), or one pair of repeated letters, or no repeated letters. There are ${4\choose2}=6$ possibilities for the first case, and $4!=24$ possibilities for the third. As for the second case, there are $2$ choices for the pair of repeated letters, ${4\choose2}=6$ ways to position them, $3$ choices for what goes in the first remaining open position, and $2$ choices for what goes in the final spot, for a total of $2\cdot6\cdot3\cdot2=72$ possibilities, and this gives an overall sum of

$$6+72+24=102$$

Barry Cipra
  • 79,832