1
$\begingroup$

I know that the generating function of the sequence counting the number of binary strings of length $n$ is $e^{2x}$. But my book doesn't explain why this is the case. Could you give me a little more insight of why it is $e^{2x}$?

$\endgroup$
3
  • 2
    $\begingroup$ $e^{2x} = \sum 2^n x^n/n!$ and $2^n$ is the number of strings $\endgroup$
    – user147263
    Jun 28, 2015 at 3:20
  • $\begingroup$ I know that, but conceptually why would we use this generating function and this approach? $\endgroup$
    – Miriam
    Jun 28, 2015 at 3:43
  • $\begingroup$ @ Miriam. "why would we use this generating function and this approach? ". Take a look at the answer provided by Brian M. Scott. The Bona reference will answer your question and it is very readable! Out of curiosity, what book are you reading that doesn't explain why exp(2*x) is the exponential generating function for binary strings. $\endgroup$ Jun 28, 2015 at 9:22

3 Answers 3

1
$\begingroup$

If you know the product theorem for exponential generating functions, the result is quite understandable. I will slightly paraphrase the version presented in Miklós Bóna, Introduction to Enumerative Combinatorics:

Theorem. Denote by $f_n$ the number of ways to carry out a task on $[n]$, and denote by $g_n$ the number of ways to carry out another task on $[n]$. Let $F(x)$ and $G(x)$ be the exponential generating functions of the sequences $\langle f_n:n\in\Bbb N\rangle$ and $\langle g_n:n\in\Bbb N\rangle$, respectively.

Let $h_n$ be the number of ways to choose a subset $S$ of $[n]$, carry out the first task on the set $S$, and then carry out the second task on the set $[n]\setminus S$. Let $H(x)$ be the exponential generating function of the sequence $\langle h_n:n\in\Bbb N\rangle$. Then $H(x)=F(x)G(x)$.

An $n$-bit string corresponds to carrying out a pair of tasks on $[n]$ in this fashion. Specifically, let $S$ be the set of bit positions that are set to $1$; $[n]\setminus S$ is then the set of bit positions that are set to $0$. The first task is simply setting all bit positions to $1$; no matter how many bits there are, there’s just one way to do this, so $f_n=1$ for each $n\in\Bbb N$. The second task is setting all bit positions to $0$, so of course we also have $g_n=1$ for all $n\in\Bbb N$. Thus,

$$F(x)=G(x)=\sum_{n\ge 0}\frac{x^n}{n!}=e^x\;,$$

and

$$H(x)=F(x)G(x)=\left(e^x\right)^2=e^{2x}\;.$$

This is analogous to the product formula for ordinary generating functions:

Theorem. Denote by $f_n$ the number of ways to carry out a task on $[n]$, and denote by $g_n$ the number of ways to carry out another task on $[n]$. Let $F(x)$ and $G(x)$ be the ordinary generating functions of the sequences $\langle f_n:n\in\Bbb N\rangle$ and $\langle g_n:n\in\Bbb N\rangle$, respectively.

Let $h_n$ be the number of ways to choose split $[n]$ into two intervals, carry out the first task on the the first interval, and then carry out the second task on the the second interval. Let $H(x)$ be the generating function of the sequence $\langle h_n:n\in\Bbb N\rangle$. Then $H(x)=F(x)G(x)$.

If we use the same tasks as before, $f_n$ and $g_n$ are again $1$ for each $n\in\Bbb N$, and $h_n$ is the number of $n$-bit strings consisting of a string $k$ ones followed by $n-k$ zeroes, where $0\le k\le n$. Clearly there are $n+1$ such strings, and this is exactly what the theorem tells us. We have

$$F(x)=G(x)=\sum_{n\ge 0}x^n=\frac1{1-x}\;,$$

so

$$H(x)=\frac1{(1-x)^2}=\frac{d}{dx}\left(\frac1{1-x}\right)=\sum_{n\ge 0}(n+1)x^n\;.$$

The difference is that ordinary generating functions are appropriate when $[n]$ is split into two intervals on which the two tasks are performed, while exponential generating functions are appropriate when $[n]$ is split into two arbitrary sets on which the two tasks are performed.

$\endgroup$
0
$\begingroup$

Perhaps this will help. First suppose you only have one symbol, so there's only one string of each length. The exponential generating function which counts these is $$\sum_{n\ge0}\frac{x^n}{n!}=e^x.$$

Now suppose you have a binary string, so there are two symbols $0$ and $1$. Say you want to know how many strings there are with $k$ zeros and $n-k$ ones. We "tag" the zeros with an indeterminate $x$, and the ones with another indeterminate $y$ as follows: the egf for strings of zeros is $e^x$, the egf for strings of ones is $e^y$, so the egf for binary strings is $e^x e^y = e^{x+y}$.

The number of strings of length $n$ with $k$ zeros and $n-k$ ones is the coefficient of $x^k y^{n-k}/n!$ in the product. But when you multiply out $$\left(1+x+\frac{x^2}{2!}+\cdots\right)\left(1+y+\frac{y^2}{2!}+\cdots\right),$$ the only pair of terms which contributes to $x^ky^{n-k}$ is to select $x^k/k!$ from the first series and $y^{n-k}/(n-k)!$ from the second one. So the coefficient of $x^k y^{n-k}/n!$ is $$\frac{n!}{k!(n-k)!}=\binom nk.$$

If you look at the degree-$n$ terms on both sides of the equation $e^xe^y=e^{x+y}$, you get $$\sum_k \frac{n!}{k!(n-k)!} x^ky^{n-k} = (x+y)^n,$$ which is usually called the binomial theorem.

If you don't care about breaking out zeros and ones separately, you can specialize this by setting $y=x$. The equation $e^xe^y=e^{x+y}$ then becomes $e^xe^x=e^{2x}$: the first $e^x$ is the egf for strings of zeros, the second $e^x$ is the egf for strings of ones, and the product is the egf for binary strings. This makes sense, as the coefficient of $x^n/n!$ in $e^{2x}$ is $2^n$, which is indeed the number of binary strings.

$\endgroup$
0
$\begingroup$

Note: This answer is a supplement to the comment of @1999.

Let $(a_n)_{n\geq 0}$ denote a sequence of numbers. We can encode this information using different kinds of generating functions. Two customary variants are

  • ordinary generating functions: $\sum_{n=0}^{\infty}a_nx^n$

  • exponential generating functions: $\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}$

Since the number of binary strings of length $n$ is $2^n$, the sequence of numbers is

\begin{align*} (a_n)_{n\geq 0}=(2^n)_{n\geq 0} \end{align*}

The corresponding ordinary generating function is \begin{align*} \sum_{n=0}^{\infty}a_nx^n=\sum_{n=0}^{\infty}2^nx^n=\sum_{n=0}^{\infty}(2x)^n=\frac{1}{1-2x} \end{align*} and the corresponding exponential generating function is \begin{align*} \sum_{n=0}^{\infty}a_nx^n=\sum_{n=0}^{\infty}2^n\frac{x^n}{n!}=\sum_{n=0}^{\infty}\frac{(2x)^n}{n!}=e^{2x} \end{align*}

We assume the empty string with length zero is also considered yielding $a_0=1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .