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