La generación de la función de las palabras en un alfabeto binario conteo de bloques y de las apariencias

Question

Dado el binario alfabeto {a,b}, estoy tratando de encontrar la generación de la función que distingue, por todas las palabras de longitud fija $n$, el número de bloques de una y el número de una. Deje $x^p$ contar el número de bloques de tamaño $p$ $y^q$ contar el número de una en una palabra. Como un primer ejemplo, toma la palabra:

abbaaabaabaabba

Esto tiene un nueve dividido en dos bloques de longitud uno, a dos cuadras de longitud, dos y un bloque de longitud tres. Esto contribuiría a la generación de la función de un plazo de $y^9(2x + 2x^2 + x^3)$.

Como un segundo ejemplo, con $n=3$ hay ocho palabras y el plazo asociados con cada uno de ellos es:

bbb = 1
bba = xy
bab = xy 
baa = (xy)^2
abb = xy
aba = 2xy^2
aab = (xy)^2
aaa = (xy)^3

Tenga en cuenta que el término aba = 2xy^2 no es un error, hay dos bloques de longitud uno. Con $A$ como la generación de función, esto daría: $A_3(x,y) = 1 + 3xy + (2x + 2x^2)y^2 + y^3x^3$. He sido capaz de llegar con un caso especial de esto, cuando no nos preocupamos de la cuenta de la una de la (equivalente a la configuración de todos los $y=1$). Esta restringido $B_n(x) = A_n(x,y=1)$ es:

$$ B_n = B_{n-1} + x^n + \sum_{j=0}^{n-2} ( 2^j x^{n-j-1} -1 + B_j ) $$

with $B_0 = 1$. Is there such a formula for $A_n$, or even better, a non-recursive closed form of $A_{npq}$?

Answer 1

Sé que esto es una muy vieja pregunta, PERO he aquí una respuesta:

En primer lugar, permítanme definir cuatro funciones...

Deje $\text{part}_{k}(n)$ devuelve el $k$th lexicográfica de la partición de $n$. Por ejemplo, $\text{part}_{0}(5) = \langle 5 \rangle$, $\text{part}_{1}(5) = \langle 4,1 \rangle$, y $\text{part}_{4}(5) = \langle 2,2,1 \rangle$.

Además, defino $\text{part}_{k,p}(n)$ $p$ésimo elemento de a $\text{part}_{k}(n)$. Por ejemplo, $\text{part}_{4,2}(5) = 1$.

A continuación, vamos a $\text{len}(\text{part}_{k}(n))$ devuelve el número de elementos en $\text{part}_{k}(n)$. Por lo tanto, $\text{len}(\text{part}_{4}(5)) = 3$.

Por último, vamos a definir $\text{count}(\text{part}_{k}(n), x)$ a ser el número de elementos en $\text{part}_{k}(n)$ con el valor de $x$. Por lo tanto, $\text{count}(\text{part}_{4}(5), 2) = 2$.

Además, aquí hay un par de definiciones de variables.

$w = $ número de caracteres en word.
$n = $ número de particiones de $w$.

Ahora podemos empezar a trabajar en la fórmula! :P

Elegí a contar de las particiones, como estoy seguro de que mi función de las definiciones implícitas. Me di cuenta de que la manera en que usted pone su problema significaba que mientras haya al menos una b entre cada bloque de una, entonces no puede haber cualquier número de b en otro lugar y la función para esa situación en particular sería igual. En otras palabras, la función de x y de y de "aaabbabbba" sería exactamente el mismo como para "baaabbbaba".

En primer lugar, me contó el número de maneras de organizar los bloques de una. Esto es equivalente a tener una fila de b y de los espacios en blanco y contar cuántas maneras para que elija el que los espacios en blanco para colocar los bloques de una en una. Por ejemplo, a dos cuadras de una ("aaa" y "aa", por ejemplo) se puede poner en 6 espacios en blanco con 5 b entre ellos ("_b_b_b_b_b_") en $\binom{6}{2} = 15$ formas (6 espacios en blanco, a 2 cuadras). En general, el número de espacios en blanco es el número de b más uno, que es
$\displaystyle \binom{w+1-\text{len}(\text{part}_{i}(k))}{\text{part}_{i}(k)}$
donde $i$ es el índice de la partición en particular y $k$ es el número de un.

A continuación, tenemos que multiplicar por el número de maneras de organizar los bloques entre sí. Prescindiendo de los duplicados, este es el factorial del número de bloques, que es $\text{len}(\text{part}_{i}(k))!$. Para dar cuenta de los duplicados, tenemos que dividir por el producto de los factoriales de el número de veces que cada elemento se repite (wow, eso fue prolijo). En todos, se parece a esto:
$\displaystyle \frac{\text{len}(\text{part}_{i}(k))!}{\displaystyle \prod_{j=0}^{k} \Bigl( \text{count}(\text{part}_{i}(k),j)! \Bigr)}$

Multiplicando los dos nos da el coeficiente de cada pieza. Las x están dadas por $\displaystyle \sum_{q=0}^{\text{len}(\text{part}_{i}(k))} x^q$, y el eje y se les da por $y^k$. Por lo tanto, la ecuación general es:

$A_{w}(x,y) = \displaystyle \sum_{k=0}^{w} \left( y^k \; \sum_{i=0}^{n} \left( \binom{w+1-\text{len}(\text{part}_{i}(k))}{\text{part}_{i}(k)} \frac{\text{len}(\text{part}_{i}(k))!}{\displaystyle \prod_{j=0}^{k} \Bigl( \text{count}(\text{part}_{i}(k),j)! \Bigr)} \right) \left( \sum_{q=0}^{\text{len}(\text{part}_{i}(k))} x^q \right) \right)$

Yep. Bastante un monstruo. Pero esto no es muy difícil de programar, aunque sin duda sería muy tedioso para hacer a mano.