¿Cómo contar el número de palabras de un alfabeto con restricciones en el número de letras?

Question

Para un alfabeto $X$ ¿existe un método para calcular cuántas palabras sobre $X$ de longitud $n$ hay donde el número de apariciones de cada letra debe satisfacer un sistema de ecuaciones?

Por ejemplo, si $|X| = 5$ . Sea ${\{a, b, c, d, e}\}$ representan el número de veces que aparece cada una de las cinco letras en una longitud $n$ palabra sobre $X$ .

Sin restricciones, creo que el número de palabras sería $5^n$ .

¿Qué pasa con el sujeto a la restricción $2a+2e=2d+2b-c$ ?

Editar: Así que tuve la idea de que podíamos formar un conjunto de palabras primos, de tal manera que cada palabra que satisface la ecuación se puede descomponer en estas palabras más pequeñas (hasta permutar las letras de la palabra original).

Etiquetar cada una de las letras ${A,B,C,D,E}$ este conjunto es $\{AD, AB, ED, EB, DCC, BCC\}$ , por lo que hay $4$ palabras primarias de longitud $2$ y $2$ de longitud $3$ a partir de la cual deben componerse todas las palabras que satisfagan la condición (hasta la permutación).

Entonces podemos obtener el número total comprobando las particiones de $n$ :

\begin {array}{|c|c|c|c|} \hline 1 & 0 \\ \hline 2 & 4 \\ \hline 3 & 2 \\ \hline 4 & 4^2=16 \\ \hline 5 & 4.2=8 \\ \hline 6 & 4^3+2^2=68 \\ \hline 7 & 4^2.2=32 \\ \hline 8 & 4^4+4.2^2=272 \\ \hline \end {array}

Por supuesto, sin restricciones, el total es ahora ${{4+n}\choose{n}}$ en lugar de $5^n$ . Esto no es realmente lo mismo que el problema original, pero tal vez sea relevante. ¿Qué opinas?

Answer 1

ampliando un poco el comentario que hice sobre el uso de autómatas no he resuelto el problema en sí, sino que podemos contar el número de palabras con la restricción de ejemplo que hiciste (es decir $2a-2b+c-2d+2e=0$ ) y añadiendo otra restricción (por cuestión de finitud del sistema) que es que para cada prefijo $x$ de la palabra, lo siguiente debe sostenerse $p\leq 2a-2b+c-2d+2e \leq q$

Se puede hacer resolviendo el siguiente sistema de series formales para $A_0$

$A_0=1+2xA_2+2xA_{-2}+xA_1$
$A_i=2xA_{i+2}+2xA_{i-2}+xA_{i+1} \hspace{5mm}$ para $i \in [p+2,q-2]\setminus \{0\}$
$A_{p}=xA_{p+1}+2xA_{p+2}$
$A_{p+1}=xA_{p+2}+2xA_{p+3}$
$A_{q}=2xA_{q-2}$
$A_{q-1}=xA_q+2xA_{q-3}$

que se gana viendo el siguiente autómata(en su forma matricial porque no sé dibujar bien :P) $ \left( \begin{array}{ccccc} 0 & 1 & 2 & 0 & 2 \\ 0 & 0 & 1 & 2 & 0 \\ 2 & 0 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 & 0 \\ 2 & 0 & 0 & 1 & 0 \end{array} \right)$

Por ejemplo, he calculado la serie generadora de palabras con $q=2,p=-2$ y es $\frac{1-4x^2}{1-12x^2-6x^3+32x^4-8x^5}=1+8x^2+6x^3+64x^4+128x^5+O(x^6)$ .

Me gusta mucho esta pregunta y espero leer pronto alguna respuesta interesante :).

Answer 2

Dejemos que $R = a+e$ , $S=b+d$ , $T=c/2$ (todos son enteros no negativos, ya que $c$ debe ser par). Entonces tenemos las condiciones

$$R + S + 2 T=n\\ R - S +T =0$$

De este sistema obtenemos:

$$ 3 S = n+ R $$ $$ T = n -2S $$$$ 2 R = n - 3 T $$

Entonces $n/3\le S \le n/2$ . Podemos comprobar que, para cada número entero $S$ en ese rango obtenemos una y sólo una solución.

Ahora, si fijamos $R,S,T$ el número de combinaciones es $$ \frac{n!}{R! \, S! \, (2T)!} 2^R 2^S$$

Por lo tanto, el número total es

$$ M=n!\sum_{S=\lceil n/3 \rceil}^{\lfloor n/2 \rfloor} \frac{2^S 2^{3S-n}}{(3S-n)! S! (2n-4S)!}= \frac{n!}{2^n}\sum_{S=\lceil n/3 \rceil}^{\lfloor n/2 \rfloor} \frac{16^S}{(3S-n)! \, S! \, (2n-4S)!}$$

Algunos valores

n M
2 8 
3 6 
4 96
5 240
10 459648 
20 4081846153216 

Podemos obtener una aproximación asimétrica mediante un argumento probabilístico. Consideremos que una palabra se genera al azar (uniformemente), entonces la variable $x=2a+2e-2d-2b+c$ puede ser la suma de $n$ variables iid $z$ tomando los valores $z=\pm 2 $ con probabilidad $2/5$ y $z=1$ con prob. $1/5$ Esto significa $E(z)=1/5$ y $\sigma^2_z = 84/25$ y el, para grandes $n$ , $x$ es aproximadamente normal con $E(x)=n/5$ y $\sigma^2_x = n \, 84/25$ . Entonces

Y $$M = 5^n P(x=0) \approx 5^n \frac{5}{\sqrt{168 \, \pi n }} \exp{\left(-\frac{n}{168}\right)}$$

El acuerdo es bastante bueno para $n >20$ (se podrían obtener mejores aproximaciones mediante expansiones de Edgeworth)

 n   5^n/M  ~1/p(x=0)
10  21.245  15.421
20  23.363  23.146
30  30.474  30.086
40  37.451  36.871
50  44.295  43.752
60  51.444  50.867