4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You are overcounting the strings containing more than one $A$ or more than two $C$s. $\endgroup$ – Jack D'Aurizio Dec 17 '17 at 4:03
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Brilliant answer, thank you. $\endgroup$ – Boots Dec 18 '17 at 2:54
  • $\begingroup$ @Boots: You're welcome! :-) $\endgroup$ – Markus Scheuer Dec 18 '17 at 6:33
2
$\begingroup$

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$:

enter image description here

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$.
$\endgroup$
2
  • $\begingroup$ This is a bit different approach from what I was hoping for. Primarily because I am hoping to understand EGFs and applying them to this problem. I think this problem can be reduced to something very simple as well since I first saw it on a short exam. $\endgroup$ – Boots Dec 17 '17 at 4:15
  • 1
    $\begingroup$ the formula for $a_{n}$ is probably a good way to do it. Because we can then write $$\sum_{n=1}^{\infty} a_{n} \frac{x^n}{n!} = \sum_{n=1}^{\infty} 3^{n} \frac{x^n}{n!} - \sum_{n=1}^{\infty}n2^{n-1} \frac{x^n}{n!} - \sum_{n=1}^{\infty} 2^{n+1} \frac{x^n}{n!} + \sum_{n=1}^{\infty}(n+1) \frac{x^n}{n!}$$ and get a closed form for it $\endgroup$ – Boots Dec 17 '17 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.