Exponencial de Generación de Función para el número de secuencias a,B,C

Question

Estoy tratando de estudiar exponencial de las funciones de generación y estoy teniendo un tiempo difícil comprensión.

Estoy con la tarea de escribir una exponencial de generación de función para el número de secuencias a,B,C de longitud n tal que existe al menos una a Una y dos C

En general, una EGF es de la forma $\sum_{n=0}^{\infty} a_{n} \frac{x^n}{n!}$ donde $a_{n}$ cuenta el número de maneras de imponer una determinada estructura en un conjunto.

El número de secuencias de longitud n que contendrá al menos una a Una, creo que $n 3^{n-1}$ porque vamos a colocar en la secuencia, para lo cual hemos $n$ opciones y, a continuación, para el resto de las $n-1$ spots, tenemos 3 opciones. La elección de dos C probablemente será similar, ${n \choose 2}\cdot 3^{n-2}$ ya que vamos a colocar dos C en nuestra secuencia y, a continuación, tienen 3 opciones para el otro $n-2$ spots.

Gracias.

Answer 1

Consideramos un alfabeto $\mathcal{V}=\{A,B,C\}$ y determinar foreach de las letras en $\mathcal{V}$ la exponencial de generación de función respetando las restricciones específicas. La resultante de la generación de la función es el producto de ellos.

Obtenemos como la generación de funciones para el

• letra: Desde la letra a tiene que ocurrir al menos una vez a la generación de la función es $$e^x-1$$

• letra B: Desde la letra B tiene que producen al menos dos veces hemos $$e^x-1-x$$

• letra C: Ya que no hay restricción para la letra C tenemos $$e^x$$

Llegamos a la conclusión de la exponencial de la generación de la función $G(x)$ es \begin{align*} \color{blue}{G(x)}&=\left(e^x-1\right)(e^x-1-x)e^x\\ &\color{blue}{=e^{3x}-(x+2)e^{2x}+(x+1)e^x} \end{align*}

Es conveniente utilizar el coeficiente de operador $[x^n]$ para denotar el coeficiente de $x^n$ de una serie.

Obtenemos para $n\geq 0$

\begin{align*} \color{blue}{n![x^n]G(x)}&=n![x^n]\left(e^{3x}-(x+2)e^{2x}+(x+1)e^x\right)\\ &=n!\left([x^n]e^{3x}-\left([x^{n-1}]+2[x^n]\right)e^{2x}+\left([x^{n-1}]+[x^n]\right)e^x\right)\\ &=3^n-\left(n2^{n-1}+2\cdot 2^{n}\right)+(n+1)\\ &\color{blue}{=3^n-n2^{n-1}-2^{n+1}+n+1} \end{align*}

Sugerencia: Usted puede encontrar la Proposición II.3 en la Analítica de la Combinatoria por P. Flajolet y R. Sedgewick útil.

Answer 2

No veo ninguna razón en particular para considerar que el EGF en lugar de la OGF. Este es un autómata de la aceptación de las cadenas de más de $\Sigma=\{A,B,C\}$ que contiene al menos un $A$, y al menos dos $C$:

Por orden de sus seis estados como $\text{Start},A,C,AC,CC,ACC$ tenemos que la matriz de transición de nuestro autómata está dada por $$ P=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 2 & 0 & 1 \\ 0 & 0 & 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 3 \end{pmatrix} $$ y el número de aceptados cadenas de longitud $n$ está dado por $$ a_n = (1,0,0,0,0,0) P^n (0,0,0,0,0,1)^T. $$ Por el Cayley-Hamilton, teorema de, $a_n$ sólo depende de la descomposición de Jordan de a $P$. Los bloques de Jordan de a $P$ $\left(\begin{smallmatrix}1 & 1 \\ 0 & 1\end{smallmatrix}\right)$, $\left(\begin{smallmatrix}2 & 1 \\ 0 & 2\end{smallmatrix}\right)$, $(2)$ y $(3)$, por lo que $$ a_n = k_1 + k_2 n + k_3 2^n + k_4 n 2^n + k_5 3^n $$ para algunos adecuado constantes $k_1,k_2,k_3,k_4,k_5$ que se puede encontrar mediante la interpolación de $a_0=a_1=a_2=0, a_3=3, a_4=22$ (calculada contando los anagramas de $ACCA,ACCB$ y $ACCC$, $12+6+4$) y $a_5=105$. De ello se desprende que la OGF de $\{a_n\}_{n\geq 0}$ es de la forma $$ \frac{\alpha+\beta x}{(1-x)^2}+\frac{\gamma+\delta x}{(1-2x)^2}+\frac{\epsilon}{1-3x}$$ y el EGF de $\{a_n\}_{n\geq 0}$ es de la forma $$ (p+qx)e^x + (r+sx)e^{2x}+ t e^{3x}. $$

En el segundo pensamiento, es probablemente el más simple recuento de las cadenas de más de $\{A,B,C\}$ con una longitud de $n$ tal que

• ellos no contienen ningún tipo de $A$: son $2^n$;
• contener al menos un $C$: son $2^n+ n 2^{n-1}$
• no contienen ningún tipo de $A$ y contener al menos un $C$: son $n+1$. Por medio de la inclusión-exclusión, $$\boxed{ a_n = 3^n - n 2^{n-1}-2^{n+1}+(n+1). }$$ En particular, la OGF es $\frac{3x^3-5x^4}{(1-x)^2(1-2x)^2(1-3x)}$ y el EGF es $e^{3x}-(x+2)e^{2x}+(x+1)e^x$.