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, this could be useful for site that use these kind of combinations to calculate prices in their products or services such as game boosting, so if you have the prices then is easier to buy overwatch boost. 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