# Counting Words

Suppose that we are given the alphabet ; a word of length : , is an ordered -tuple whose elements all came from . For example, a word of length in might be the tuple , which we will hereon denote as . For some natural number , how many words of length are there that contains exactly zeros?

- 9 November, 2013 -
- Article, Math Problems -
- Tags : algebra, combinatorics, dynamic programming
- 0 Comments

### 1. The Combinatorial (Easy) Approach

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

and permuting it in every possible way, excluding overlaps. Now, there are permutations of , but of those are zero-overlapped and of those are overlapped, so there are

unique permutations of a single word . How many possible s can we possibly make? Well, there are ‘s that we can fill out and each of these can take any value besides , so there are such words, therefore there are

words of length with exactly zeros.

### 2. The Computer Scientist’s (Convoluted) Approach

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

If we make a table of this

Hmm, there doesn’t seem to be an obvious pattern here. Since we know that , let’s attempt to do this inductively on :

We know that

Great, let’s go on to the case

For the case, we would get

and inductively, because

we have that

which we derived earlier.