Serie generadora para cadena binaria con función de peso, w(x)= (número de 1's en la cadena) + (longitud de la cadena)

Question

Para una cadena binaria $s$ defina su peso $w(s)$ el número de $1$ de la cadena más la longitud de la propia cadena. Por ejemplo, $w(101101) = 10$ . Quiero encontrar la serie generatriz del conjunto $T$ de todas las cadenas binarias.

He utilizado un argumento combinatorio para demostrar que $w(s) = 2^n + \frac{n(n+1)}2$ .

• $\sum_{k=0}^n {n \choose k} + k $ donde $k$ es el número de unos de la cadena

Sin embargo, mi libro de texto pide utilizar el lema del producto para obtener la serie generatriz de una cadena de longitud $n$ . ¿Cómo podría resolver este problema utilizando ese método?

Answer 1

La función generadora de todas las cadenas, que llamaré $W(x)$ es, por definición $$ W(x) = \sum_s x^{w(s)}, $$ donde $s$ abarca todas las cadenas binarias. Parece que primero quieres encontrar la función generadora sólo para cadenas de longitud $n$ , que es lo primero que quieres encontrar $$ W_n(x)=\sum_{s\,:\,\text{len}(s)=n}x^{w(s)}, $$ y quieres encontrarlo usando el lema del producto. Esto significa que quieres expresar cadenas de longitud $n$ como una concatenación de conjuntos más pequeños de cadenas y, a continuación, calcular $W_n(x)$ como los productos de esas funciones generadoras más pequeñas.

Dado que una cadena de longitud $n$ es una concatenación de $n$ cadenas de longitud $1$ la función generadora de cadenas de longitud $n$ es sólo $$ W_n(x)=W_1(x)\times \dots\times W_1(x)=[W_1(x)]^n $$ Afortunadamente, $W_1(x)$ es simple; hay dos cadenas de longitud $1$ que tiene peso $1$ el otro con peso $2$ Así que $W_1(x)=x+x^2$ .

Por último, en última instancia, quería encontrar $W(x)$ la f.g. de todas las cuerdas. Se obtiene sumando $W_n(x)$ sobre todo $n$ : $$ W(x)=W_0(x)+W_1(x)+W_2(x)+\dots $$