How many possible phone words exist for a phone number of length N when also counting words less than length N within that phone number?

Question

The phone words problem

find all possible words that can be derived from a phone keypad, "words" do not have to be English dictionary words, for this question, words can be any combination of letters which can be mapped from a digit.

For those not familiar, phone keypads often have letters under most digits:

╔═════╦═════╦═════╗
║  1  ║  2  ║  3  ║
║     ║ abc ║ def ║
╠═════╬═════╬═════╣
║  4  ║  5  ║  6  ║
║ ghi ║ jkl ║ mno ║
╠═════╬═════╬═════╣
║  7  ║  8  ║  9  ║
║ pqrs║ tuv ║wxyz ║
╠═════╬═════╬═════╣
║  *  ║  0  ║  #  ║
║     ║     ║     ║
╚═════╩═════╩═════╝

Counting only phone words with length $n$

Here's an example to get an idea of the phone words problem: given a phone number 366, you could generate the following phone words

"dmm", "dmn", "dmo", "dnm", "dnn", "dno", "dom", "don", "doo", "emm", "emn", "emo", "enm", "enn", "eno", "eom", "eon", "eoo", "fmm", "fmn", "fmo", "fnm", "fnn", "fno", "fom", "fon", "foo"

Because 3 can be replaced by either "d", "e" or "f", and 6 can be replaced by either "m", "n" or "o". The upper bound on the number of phone words of length $n$ for a number with $n$ digits is $4^n$ (most keys have 3 letters but 7 and 9 both map to 4 letters).

Counting all words up to and including length $n$

The example above gives us 27 words, but we were only counting words whose length equals the number of digits of the phone number 366. What if we want to find all words including those whose length is less than the phone number? For example, given the same input as before, 366, you could also have generated words "no", "on", "n", etc.... How many total phone words can be generated for a phone number of length $n$?

To put this another way

Given a phone number of length $n$, we can generate $4^n$ phone words of length $n$, we can also generate $2(4^{n-1})$ phone words for each sub phone number with length $n-1$ (using the example above, that would be all phone words of 36 and 66), then all phone words for all possible sub phone numbers of length $n-2$ etc.. How many phone words are there for a phone number of length $n$ if we count all phone words possibilities or all lengths less than $n$?

Attempt at an answer

Attempting to string the above description into an equation:

$W = 4^{n} + 2(4^{n-1}) + 3(4^{n-2}) + \ldots + n$

But not sure where to go with this.

Terminology

Phone number is an ordered sequence of numerical digits. Example: 1234560, 366 etc...

Phone word is an ordered sequence of latin alphabetical characters (found on En-US telephone key pads).

• Each phone word can be directly mapped to exactly one phone number of the same length. For example: "foo" can be mapped to 366.
• Each phone number may be mapped to zero or more phone words.

Sub phone number: Given a phone number, there are $n(n+1)/2$ ways to "slice" the number into smaller phone numbers (without changing the order of the numbers). For example: 366 contains the following sub phone numbers: 36, 66, 3, 6, 6

Answer 1

[2015-12-10] Update: Thanks to a comment from @JohnMachacek I could include a reference to a paper proving the conjecture about tight upper bounds.

---

Note: This is a partial answer addressing some upper bounds and looking at some special cases. But first I like to state the problem.

Current Situation:

We consider phone numbers as non-empty strings build from an alphabet $$\mathcal{A}=\{2,3,4,5,6,7,8,9\}$$ We ignore the digits $0$ and $1$ as the corresponding keys of OPs phone keypad do not contribute any alphabetical characters. Digits from $\mathcal{A}$ are mapped to either three or four characters. So, the digits are associated with weights of size $3$ or $4$.

For convenience only we simplify the problem and consider the same weight $m>0$ for each digit in $\mathcal{A}$.

OP is asking for the number $\varphi(w)$ of words and all subwords, which can be associated with a given phone number $w$ of length $n$. We can reformulate this problem by asking for all substrings of $w$, weighted with weight $m$ accordingly.

Example: If we look at the two phone numbers $3633$ and $3336$ both having length $w=4$, we get following substrings

\begin{align*} 3633&\quad\rightarrow\quad \{3633,363,633,33,36,63,3,6\}\\ 3336&\quad\rightarrow\quad \{3336,333,336,33,36,3,6\} \end{align*}

We observe, that even if the words contain the same digits together with the same multiplicities, the number of substrings is different according to the constellation of the blocks consisting of equal digits. While $3633$ has three different substrings of length two, the string $3336$ has two different substrings of length two. We obtain with respect to the number of substrings: \begin{align*} \varphi(3633)&=m^4+2m^3+\color{blue}{3}m^2+2m\\ \varphi(3336)&=m^4+2m^3+\color{blue}{2}m^2+2m\\ \end{align*}

Upper bounds

Finding a generating function which provides the distribution of $\varphi(w)$ for all different phone numbers of length $n$ is (regrettably) beyond the scope of this answer. But we can at least provide some upper bounds for all words of length $n$. If we consider a word $w$ of length $n$ and a substring of length $k, 1\leq k \leq n$ there are two limitations:

• The number of substrings of length $k$ is limited by the size of the alphabet $\mathcal{A}$.

• There are at most $n-k+1$ substrings of length $k$ in a word of length $n$.

Since the number of substrings of length $k$ is less or equal $\min\{|\mathcal{A}|^k,n-k+1\}$ we conclude: An upper bound for $\varphi(w)$ with length of $w$ equal to $n$ is \begin{align*} \varphi(w)\leq\sum_{k=1}^{n}\min\left\{|\mathcal{A}|^k,n-k+1\right\}m^k\tag{1} \end{align*}

If we do not consider the size of the alphabet, we can provide a closed expression for a somewhat larger upper bound and claim

The following is an upper bound for $\varphi(w)$ with length of $w$ equal $n$

\begin{align*} \varphi(w)\leq\frac{m\left(m^{n+1}-m(n+1)+n\right)}{(m-1)^2}\tag{2} \end{align*}

This holds true since according to (1) \begin{align*} \varphi(w)&\leq\sum_{k=1}^{n}\min\left\{|\mathcal{A}|^k,n-k+1\right\}m^k\\ &\leq\sum_{k=1}^{n}(n-k+1)m^k\\ &=(n+1)\sum_{k=1}^{n}m^k-\sum_{k=1}^{n}km^k\tag{3} \end{align*} Using the formula for the finite geometric series we get \begin{align*} \sum_{k=1}^{n}m^k&=\frac{1-m^{n+1}}{1-m}-1=m\frac{1-m^n}{1-m}\\ \sum_{k=1}^{n}km^k&=m\sum_{k=1}^nkm^{k-1}\\ &=m\frac{d}{dm}\left(\sum_{k=1}^nm^k\right)\\ &=m\frac{d}{dm}\left(\frac{m-m^{n+1}}{1-m}\right)\\ &=m\frac{nm^{n+1}-(n+1)m^n+1}{(1-m)^2} \end{align*} Putting these two results into (3) and the claim (2) follows.

Note: The closed expression (2) is not necessarily a tight bound. If we consider e.g. the current problem with an alphabet of size $7$ we observe the expression (1) produces closer bounds for words with length $n>7$.

With $|\mathcal{A}|=7$ and weight $m=3$ according to three characters for each digit we get following upper bounds for small values of $n$

\begin{array}{rcccccccccc} n&1&2&3&4&5&6&7&8&9&10\\ \text{upper bound (1)}&3&15&54&174&537&1629&4908&\color{blue}{14745}&\color{blue}{44265}&\color{blue}{132834}\\ \text{upper bound (2)}&3&15&54&174&537&1629&4908&14748&44271&132843\\ \end{array}

Tight upper bounds

In the comment section of the OEIS sequence A094913 an interesting conjecture claims the upper bound (1) is for binary alphabets even a tight upper bound.

In fact even more is true. For each number $n>0$ and each alphabet of size $t>0$ the expression at the RHS of (1) is a maximum.

This is stated in Theorem 8 of the paper Strings with Maximally Many Distinct Subsequences and Substrings by A. Flaxman, etal. The maximum can be achieved by a modified De Bruijn word.

Answer 2

Sometimes in problems like this, it's useful to consider algorithms that generate the answer. Consider the following python code:

def num_words(phone_number):
  n = len(phone_number)
  words = []
  for i in {0, ... , n - 2}:
    for j in {i + 1, ... , n - 1}:
      words += generate_words(phone_number[i:j])
  return words

Here s[i:j] produces the substring running from index i to index j and generate_words(s) returns a list of words creatable from exactly the string s, as you do in your first list of words. It should be clear that this code produces the list that you want, so now we just need to figure out how big the list "words" is. Let's assume every key has m letters on it, so that our formula gives us both a lower bound (at $m=3$) and an upper bound (at $m=4$). Converting directly from this program into a sum gives us $$\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}|S_{i,j}|$$ where $S_{i,j}$ is the list given by the generate words function called on a string running from index i to index j.

This is a common visualization technique in combinatorics, as computer programs that answer questions tend to make it clear how subproblems are iterated over. At each step in the program, however many words are in the list "generate_words(phone_number[i:j])" get added to the total list of words, so at every step of the sum we should be adding the corresponding quantity, which is defined to be $|S_{i,j}|$. When counting the total number of words, the for loops convert directly into summation symbols with the same bounds of summation due to the "+=".

Notice that the value of $|S_{i,j}|$ doesn't actually depend on $i,j$'s values, merely their difference. This gives us the formula (remember, assuming every key has $m$ letters): $$\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}m^{j-i}=\frac{m(m^n-mn+n-1)}{(m-1)^2}$$

Where the value of the sum is computed via Wolfram Alpha. Plugging in our values of $m$ to get upper and lower bounds yields $\frac{3}{4}(3^n-2n-1)\leq N \leq \frac{4}{9}(4^n-3n-1)$. Obtaining precise values is likely to be very hard, as introducing an indicator function for a character having options of being 4 (instead of 3) letters makes the sum impossible to simplify meaningfully, as it's rather sensitive to the exact positioning of $4$ letter numbers within the broader string.

The above implicitly assumes $n>1$, so we can separately note that the answer for $n=1$ is $m$ (as both an upper and a lower bound).

Answer 3

I'll reestablish some of the things you've already stated, so that the argument is a bit more complete.

Note that I will only establish a strict upper and lower bound for the amount of phone words (as defined by you).

---

For each phone number $p_n$ of length $n$ there are $2$ sub-numbers of length $n-1$. Each of these have $2$ sub-numbers of length $n-2$. However, at least two of them are identical (consider for instance $\{3415, \{341, 415\}, \{34, 41, 41, 15\}\}$. Consequently the count of distinct sub-numbers of length $n-2$ is 3. By induction this behaviour continues.

Let $w_n$ be the upper bound of the amount of all phone words of length $\ell =n$ we can generate with a phone-word of length $n$. Obviously

$$w_n = 4^n$$

Let then $W_n$ be the upper bound of the amount of all phone words of length $\ell \in [1, n]$ we can generate with phone-word of length $n$. Now we get

$$W_n = w_n + 2\cdot w_{n-1} + 3 \cdot w_{n-2} \dots = \sum_{k=1}^{n} (n-k + 1)\cdot 4^k = (n+1)\sum_{k=1}^{n}4^k - \sum_{k=1}^{n}k\cdot4^k$$

The first series is a plain geometric series, the second one is a bit more tricky, I am in fact not sure how to solve it, but my favorite CAS gave me the following result:

$$\begin{align} W_n &= (n+1)\sum_{k=1}^{n}4^k - \sum_{k=1}^{n}k\cdot4^k = (n+1)\cdot\underbrace{\frac{4}{3}(4^n - 1)}_{\text{First sum}} - \underbrace{\frac{4}{9}(1-4^n+3\cdot 4^n\cdot n)}_{\text{Second sum, magic}} \\ \end{align}$$

Note that you didn't ask for it but I'll just note what the lower bound is, as we've found an upper bound. The lower bound , call it $\omega_n$ occurs when a phone number is a sequence of repeating digits not equal to $7$ or $9$. It then only has $1$ unique sub number, and consequently:

$$\omega_n = 3^n + 3^{n-1} \dots = \sum_ {k=1}^{n}3^k = \frac{3}{2}(3^n - 1)$$

Answer 4

There are a few ways to interpret the question, but chiefly I see two:

1. Given a specific phone number $d_1, d_2, \dots, d_n$, with $d_i$ digits between $0-9$, how many "phone words" does it contain. More precisely, take the set of all non-empty words over the $26$ letter alphabet. An $m$ letter word $w$ in this set can be represented by $c_1, c_2, \dots, c_m$, where each $c_i$ is one of the $26$ letters. We then say a number $d_1, d_2, \dots, d_n$ "contains" a word $c_1, c_2, \dots, c_m$ with iff there is some $1 \leq i \leq j \leq n$ such that $d_i, d_{i+1}, \dots, d_j$ matches $c_1, c_2, \dots, c_m$. We say that a string of digits "matches" a string of characters (a word) iff typing that string of digits on a phone keypad can result in that word (a more precise definition is possible, but not necessary I think).

2. Given the set of all phone numbers of length $n$, starting at $\overbrace{0, 0, \dots, 0}^\text{$n$ times}$ and ending at $\overbrace{9, 9, \dots, 9}^\text{$n$ times}$, how many phone words are there such that there exists some phone number in our set that contains the word? Contains is in the same sense as above.

I believe the other questions address case $(1)$, which is by far the harder case. For completeness, I will answer case $(2)$ here, but I warn a reader of this post that the answer is not very exciting. We simply observe that any word of length less than $n$ is contained in some number of length $n$. In fact, it is contained in many a number. To construct just one of these numbers, simply type the numbers on the phone keypad corresponding to the given word, and fill in the rest with whatever you like. Thus the question reduces to: how many words of length $n$ or less can be formed from the $26$ letter alphabet? There are $26$ one letter words, $26^2$ two letter words, $26^3$ three letter words, and so on. So the answer is simply the geometric sum:

$$26 + 26^2 + \dots + 26^n = \dfrac{26^{n+1} - 26}{25}$$