# Sort of Combination with repetitions

How many string exist of length 2M with 9 characters and without repeating a character more than M times? You can suppose that M is greater than 4.

I know that my english is really bad so i'll give you some examples.

Suppose M=5.
AABBCCDDEE is a valid string
AAAAAADEEE is not a valid string (A is repeated more then 5 times).
AA is not a valid string as it is not of length 2M
ZZ is not a valid string as you can have 9 different chars :A,B,C,D,E, F, G, H, I.

p.s. Is not homework: the original question is really different, I'm asking you a simplified model.

Thank you.

-
Do you require that the string be in alphabetic order? All your examples are that way. For M=5, how about EEDDCCBBAA? Also, a prior edit seemed to allow ABCDEFGHI, but now you only allow M different characters instead of specifically 9-is this correct? If so, you could correct the first line of the question. –  Ross Millikan Jan 26 '11 at 18:12
I talk about combination, i thought that means order doesn't matter. ABCEDFGHI Is not a valid string, it is of length 9 and not of length 2M. Different characters can be in any number. –  Fabio F. Jan 26 '11 at 18:14

Assuming order does not matter (i.e. you are looking for sorted strings), you are looking for the number of solutions of

$$x_1 + x_2 + \dots +x_9 = 2M$$

where $0 \le x_i \le M$.

This is same the coefficient of $x^{2M}$ in

$$(1+x+x^2 + \dots + x^{M})^9 = (x^{M+1} - 1)^9 \times (x-1)^{-9}$$

which gives us (using binomial theorem for $9$ and $-9$)

$$9 \ (-1)^{M} \ \binom{9+M-1-1}{9} + \binom{9 + 2M -1}{9}$$

$$= 9 \ (-1)^{M} \ \binom{7+M}{9} + \binom{8 + 2M}{9}$$

-
I thought that the answer would be easier! Thank you –  Fabio F. Jan 26 '11 at 21:26
@Fabio: I am pretty sure there are easier answers! I mentioned this method as it is quite powerful :-) –  Aryabhata Jan 26 '11 at 22:25