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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 26, 2011 at 18:12
  • $\begingroup$ 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. $\endgroup$ Jan 26, 2011 at 18:14

1 Answer 1

4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I thought that the answer would be easier! Thank you $\endgroup$ Jan 26, 2011 at 21:26
  • $\begingroup$ @Fabio: I am pretty sure there are easier answers! I mentioned this method as it is quite powerful :-) $\endgroup$
    – Aryabhata
    Jan 26, 2011 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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