Exponential Generating Function for the number of sequences in A,B,C

Question

I am trying to study exponential generating functions and I am having a difficult time understanding.

I am tasked with writing an exponential generating function for the number of sequences in A,B,C of length n such that there is at least one A and two C's.

In general, an EGF is of the form $\sum_{n=0}^{\infty} a_{n} \frac{x^n}{n!}$ where $a_{n}$ counts the number of ways to impose a certain structure on a set.

The number of sequences of length n that will contain at least one A is I believe $n 3^{n-1}$ because we will place an A in the sequence, for which we have $n$ choices, and then for the remaining $n-1$ spots, we have 3 choices. Choosing two C's will probably be similar, ${n \choose 2}\cdot 3^{n-2}$ since we will place two C's in our sequence, and then have 3 choices for the other $n-2$ spots.

Thank you.

Answer 1

We consider an alphabet $\mathcal{V}=\{A,B,C\}$ and determine foreach of the letters in $\mathcal{V}$ the exponential generating function by respecting the specific restrictions. The resulting generating function is the product of them.

We obtain as generating functions for the

• letter A: Since the letter A has to occur at least once the generating function is $$e^x-1$$

• letter B: Since the letter B has to occur at least twice we have $$e^x-1-x$$

• letter C: Since there is no restriction for the letter C we have $$e^x$$

We conclude the exponential generating function $G(x)$ is \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*}

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain for $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*}

Hint: You might find Proposition II.3 in Analytic Combinatorics by P. Flajolet and R. Sedgewick helpful.

Answer 2

I do not see any particular reason for considering the EGF instead of the OGF. This is an automaton accepting the strings over $\Sigma=\{A,B,C\}$ containing at least one $A$ and at least two $C$:

By ordering its six states as $\text{Start},A,C,AC,CC,ACC$ we have that the transition matrix of our automaton is given by $$ 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} $$ and the number of accepted strings of length $n$ is given by $$ a_n = (1,0,0,0,0,0) P^n (0,0,0,0,0,1)^T. $$ By the Cayley-Hamilton theorem, $a_n$ only depends on the Jordan decomposition of $P$. The Jordan blocks of $P$ are $\left(\begin{smallmatrix}1 & 1 \\ 0 & 1\end{smallmatrix}\right)$, $\left(\begin{smallmatrix}2 & 1 \\ 0 & 2\end{smallmatrix}\right)$, $(2)$ and $(3)$, so $$ a_n = k_1 + k_2 n + k_3 2^n + k_4 n 2^n + k_5 3^n $$ for some suitable constants $k_1,k_2,k_3,k_4,k_5$ which can be found by interpolating $a_0=a_1=a_2=0, a_3=3, a_4=22$ (computed by counting the anagrams of $ACCA,ACCB$ and $ACCC$, $12+6+4$) and $a_5=105$. It follows that the OGF of $\{a_n\}_{n\geq 0}$ is of the form $$ \frac{\alpha+\beta x}{(1-x)^2}+\frac{\gamma+\delta x}{(1-2x)^2}+\frac{\epsilon}{1-3x}$$ and the EGF of $\{a_n\}_{n\geq 0}$ is of the form $$ (p+qx)e^x + (r+sx)e^{2x}+ t e^{3x}. $$

On second thought, it is probably simpler to count the strings over $\{A,B,C\}$ with length $n$ such that

• they do not contain any $A$: they are $2^n$;
• contain at most one $C$: they are $2^n+ n 2^{n-1}$
• do not contain any $A$ and contain at most one $C$: they are $n+1$. By inclusion-exclusion, $$\boxed{ a_n = 3^n - n 2^{n-1}-2^{n+1}+(n+1). }$$ In particular the OGF is $\frac{3x^3-5x^4}{(1-x)^2(1-2x)^2(1-3x)}$ and the EGF is $e^{3x}-(x+2)e^{2x}+(x+1)e^x$.