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