# Counting words of varying length made out of a restricted alphabet

I have letters 'a', 'b', and 'c'. What's the formula to get all possible combinations? Like for 'a' and 'b' would be: 'a', 'b', 'aa','ab', 'ba' and 'bb'. And what is this called, Permutations?

-
@Eivind: Thank you for pointing out my error. – JavaMan Jun 16 '11 at 14:01
It's not a permutation. In a permutation, the number of objects is kept constant. You have the same number of objects (and also the same objects) before you permute as after. – please delete me Jun 16 '11 at 14:06
Definitely not combinations. Not really the usual meaning of permutations. You are counting "words". You can find the number of $1$-letter words, of $2$-letter words, of $3$-letter words, by listing and counting. This experimentation will reveal patterns. – André Nicolas Jun 16 '11 at 14:10

Given $n$ symbols $X_1,\dots,X_n$ there are $n^i$ words of length exactly $i$ (if you allow words with repeating characters).

Hence, if you wish to know the number of words of length less than or equal to $y$ you may use the formula

$$\sum_{i=0}^{i=y} n^i = \frac{1-n^{y+1}}{1-n}$$

or if you wish to exclude the empty word

$$\sum_{i=1}^{i=y} n^i = \frac{1-n^{y+1}}{1-n} - 1$$

-
Did you mean to write $n^i$ instead of $i^n$? – Shai Covo Jun 16 '11 at 14:25
yup. ${}$${}$${}$ – jspecter Jun 16 '11 at 14:27
What is n, y and i? – Cobold Jun 16 '11 at 14:47
$n$ is the number of symbols (a, b, c, ...) and $y$ is the maximum word length you are considering. So for symbols (a,b) and words of length two or less, you have $n=2$ and $y=2$. Here $i$ is a dummy variable used for the summation. – Chris Taylor Jun 16 '11 at 14:50
They're natural numbers. $n$ is the number of symbols (letters) in your alphabet, i.e. the number of symbols you have to choose from. In your example your alphabet consists of three letters $a,b,c$ so $n = 3.$ The numbers $i,y$ represent word lengths. A word is a concatenation of letters from your alphabet. For example $ab,b,abbab$ are words. The length of a word is the number of letters which appear. The formula which I gave is for the number of words less than some length $y.$ – jspecter Jun 16 '11 at 14:55

I will deal with the problem in a style much like the one in which you posed the problem. But the right approach is the more general one of jspecter's answer, and it is important that you try to master it.

We look at the "alphabet" that consists of the $3$ letters $a$, $b$, and $c$. To use set-theoretic language, we are working over the alphabet $\{a,b,c\}$.

First we ask: how many $1$-letter words are there? The answer is immediate: there are $3$ of them, namely the words $a$, $b$, and $c$.

Now we ask: how many $2$-letter words are there? We will list them and count. For various reasons, it is very important that we list the words in some systematic way. For one thing, if we do it systematically, we will be unlikely to miss a word, or to list it twice. And, as you will see, there are even better reasons.

The best listing for our purposes is the usual alphabetic listing. To use fancy language, we are listing the words in lexicographic (dictionary) order. The $2$-letter words are: $aa$ $ab$ $ac$ $ba$ $bb$ $bc$ $ca$ $cb$ $cc$

Count. There are $9$ $2$-letter words.

Now what about $3$-letter words. I really should list them all, but that sounds like work. So I will take a shortcut. Instead of actually listing, I will imagine listing.

How many $3$-letter words begin with $a$? To make a $3$-letter word that begins with $a$, we write down $a$, and append to it any of our $9$ $2$-letter words. So there are $9$ $3$-letter words that begin with $a$.

Similarly, there are $9$ $3$-letter words that begin with $b$, and $9$ that begin with $c$. If you imagine putting the $3$-letter word that begin with $a$ on one page, the ones that begin with $b$ on the next page, and the ones that begin with $c$ on the next page, there will be $3$ pages, with $9$ words on each page, for a total of $3\times 9$, that is, $27$.

How many $4$-letter words are there? First, how many begin with $a$? You get such a word by appending any $3$-letter word to $a$, so there are $27$ $3$-letter words that begin with $a$. There are also $27$ that begin with $b$, and $27$ that begin with $c$, for a total of $81$.

Now can you see instantly how many $5$-letter words there are using the alphabet $\{a,b,c\}$?

In general, by the same reasoning, there will be $3^n$ $n$-letter words using this alphabet.

OK, we have sort of dealt with what's happening with $3$ letters. What about if we have a $4$-letter alphabet $\{a,b,c,d\}$?

Clearly there are $4$ $1$-letter words. How many $2$-letter words? How many $2$-letter words begin with $a$? You write down $a$, and append any $1$-letter word, so there are $4$. There are also $4$ $2$-letter words that begin with $b$, and $4$ that begin with $c$, and $4$ that begin with $d$, for a total of $16$, or, as I prefer to put it, $4^2$.

Try to see why there are $4^3$ $3$-letter words over our new alphabet.

Now for something fancier, closely related to what you were asking. We suppose our alphabet has $3$ letters, and are told that the only "legal" words are words with $1$ to $10$ letters. What is the total number of legal words?

Well, there are $3$ $1$-letter words, and $3^2$ $2$-letter words, and so on up to $3^{10}$ $10$-letter words. So the total is $$3+3^2+3^3+\cdots +3^9+3^{10}$$

We could calculate each term individually, and add them up. But there is a shortcut. I will not write further, but we are dealing here with what is called a geometric series, or geometric progression. (If you have forgotten, look it up in Wikipedia.)

There is a nice formula for the sum of a geometric progression, so you can obtain a pleasant and much shorter expression for the long sum $3+\cdots +3^{10}$.

-
Thank you for explaining everything clearly! Very help full! – Cobold Jun 16 '11 at 17:57

These are called

tuples

or vectors. If the number of positions is 2 or 3, then they are (ordered) pairs or triples respectively.

You have a string of length $k$, and in each position you can have any of $n$ possibilities. To count all the possibilities you choose independently 1 out of $n$ for each position, so $n$ times $n$ times ... times $n$, for $k$ positions, or

$$n^k.$$

For any length less than or equal to $k$, sum over 1 to $k$.

The terms combination and permutation are for collections where you don't allow repeats ('without replacement'). Look for Stanley's 'Twelve fold way' to put all these ways of organizing elements into a grander scheme.

-

Some sort of sum of permutations? I'm afraid I don't know what else to call it. But you are taking every single possible permutation of elements from a set of $k$ elements. You're then looking at something like this: \begin{align} {}_kP_1 + {}_kP_2 + \dotsb + {}_kP_k = \sum_{i=0}^k {}_kP_i \end{align}