Especie de Combinación con repeticiones

Question

Cuántos cadena de longitud 2M con 9 caracteres y sin repetir un personaje más de M veces? Usted puede suponer que M es mayor que 4.

Yo sé que mi inglés es muy malo así que me voy a dar algunos ejemplos.

Supongamos Que M=5.
AABBCCDDEE es una cadena válida
AAAAAADEEE no es una cadena válida (se repite más de 5 veces).
AA no es una cadena válida, ya que no es de longitud 2M
ZZ no es una cadena válida, como se puede tener 9 diferentes caracteres :a,B,C,D,E, F, G, H, I.

p.s. No es la tarea: la pregunta original es muy diferente, yo estoy pidiendo que un modelo simplificado.

Gracias.

Answer 1

Suponiendo que no importa el orden (es decir, usted está buscando ordenados cadenas), se busca el número de soluciones de

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

donde $0 \le x_i \le M$.

Este es el mismo que el coeficiente de $x^{2M}$ en

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

lo que nos da (usando el teorema del binomio para$9$$-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}$$