Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.