4
$\begingroup$

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.

  • 0
    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.2011-01-26

1 Answers 1

4

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}$

  • 0
    @Fabio: I am pretty sure there are easier answers! I mentioned this method as it is quite powerful :-)2011-01-26