Add Me!Close Menu Navigation

Counting Words

Suppose that we are given the alphabet \Sigma = \Rec{0,1,2}; a word of length n: x_n \in \Sigma^5, is an ordered n-tuple whose elements all came from \Sigma. For example, a word of length 5 in \Sigma might be the tuple (0,0,2,1,0), which we will hereon denote as 00210. For some natural number k \le n, how many words of length n are there that contains exactly k zeros?

1. The Combinatorial (Easy) Approach

Consider the placement of the zeros in an n-word: this is equivalent to the problem where we choose an arbitrary word prefixed with k zeros, like

    \[w_n = 0\stackrel{k}{\cdots}0\sigma_{k+1}\sigma_{k+2}\cdots\sigma_n\]

and permuting it in every possible way, excluding overlaps. Now, there are n! permutations of w_n, but k! of those are zero-overlapped and n-k of those are \sigma overlapped, so there are

    \[\frac{n!}{k!(n-k)!} = {n \choose k}\]

unique permutations of a single word w_n. How many possible w_ns can we possibly make? Well, there are n-k \sigma_i‘s that we can fill out and each of these can take any value besides 0, so there are 2^{n-k} such words, therefore there are

    \[{n \choose k}2^{n-k}\]

words of length n with exactly k zeros.

2. The Computer Scientist’s (Convoluted) Approach

We can boil this down into a decision problem. Suppose we use the decision variable a_n^k to denote the total number of words of length n with exactly k zeros, then we can consider a component-by-component decision problem. At each cell of the word, we can either fill in a 0, or a 1/2. Suppose we begin at the left end of the word, if we fill in a 0 at the current slot, then there are a_{n-1}^{k-1} words available to us (because we used up one slot, so decrease n by 1, and we used up one zero, so decrease k by 1), and if we fill in either a 1 or a 2, then we still have k zeros to choose from, so there are a_{n-1}^k such words available to us. Combining the two together (in the spirit of dynamic programming), we get the recurrence

    \begin{align*} a_n^k &= 2a_{n-1}^k + a_{n-1}^{k-1} \\ a_n^0 &= 2a_{n-1}^0 = 2^n \\ a_n^n &= 1 \end{align*}

If we make a table of this

    \[\begin{array}{|c|cccccc|} \hline n\k & 0 & 1 & 2 & 3 & 4 & 5\\ \hline 0 & 1 & & & & & \\ 1 & 2 & 1 &&&& \\ 2 & 4 & 4 & 1 &&& \\ 3 & 8 & 12 & 6 & 1 && \\ 4 & 16 & 32 & 24 & 8 & 1 & \\ 5 & 32 & 80 & 80 & 40 & 10 & 1 \\ \hline \end{array}\]

Hmm, there doesn’t seem to be an obvious pattern here. Since we know that a_n^0 = 2^n, let’s attempt to do this inductively on k:

We know that

    \begin{align*} a_n^1 &= 2^{n-1} + 2a_{n-1}^1 \\ \intertext{dividing both sides by $2^n$, we get} \\ \frac{a_n^1}{2^n} &= 2^{-1} + \frac{a_n^1}{2^{n-1}} \\ \intertext{let $b_n^1 = a_n^12^{-n}$, then} b_n^1 &= 2^{-1} + b_{n-1}^1 \\ b_n^1 &= n2^{-1} \\ a_n^1 &= n2^{n-1} \end{align*}

Great, let’s go on to the k = 2 case

    \begin{align*} a_n^2 &= a_{n-1}^1 + 2a_{n-1}^2 \\ &= (n-1)2^{n-2} + 2a_{n-1}^2 \\ b_n^2 &= a_n^2 2^{-n} \\ b_n^2 &= (n-1)2^{-2} + b_{n-1}^2 \\ b_n^2 &= \sum_{k=1}^n (k-1)2^{-2} \\ &= {n \choose 2} 2^{-2} \\ a_n^2 &= {n \choose 2} 2^{n-2} \end{align*}

For the k=3 case, we would get

    \[b_n^3 = 2^{-3} \sum_{k=2}^{n} {k \choose 2} = 2^{-3} {n \choose 3}\]

and inductively, because

    \[b_n^{k+1} = 2^{-k} \sum_{i=k}^{n} {i \choose k} = 2^{-k} {n \choose k} ~~~~ \blacksquare\]

we have that

    \[a_n^k = {n\choose k}2^{n-k}\]

which we derived earlier.

Posted By Lee

Woosh

Recent Comments