Exponential generating function for the number of binary strings of length $n$

Question

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}$?

Answer 1

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.

Answer 2

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.

Answer 3

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