Limit the maximum value of the composition of an integer

Question

I was doing a coding test (already finished, so no cheating for me) and came across this problem, which I'll describe in few steps:

1. We have a keypad, like on cellphones, with keys from 1 to 9, where 1 is the space key (" ")
2. We are given a message to convert to numbers based on the "distance" of each letter (P = 7, S = 7777, K = 55, ...), for example DRSA becomes 377777772
3. Now we need to calculate the the number of the possible messages we could write with that same number (DPPPPPPPA, DPPPPPQA, ...)

---

The method I came up with is the following:

1. I split the number by its different digits obtaining for example 3, 7777777, 2
2. I ignored single digits as they do not add "value" to the permutations (as far as I understood it)
3. I take each section of digits and based on its length (in this case 7 digits) I calculate every possible permutation and count them

---

Now this method works, but it's slow so I wanted to find a way to calculate the number of these permutations without counting them manually.

I found out about integer compositions, which in my case should have a maximum value. In this case the key 7 has a maximum value of 4 so its composition would be something like this:

• 4+3
• 3+4
• 4+1+2
• 4+2+1
• 1+2+4
• 1+4+2
• ...

How can I limit the maximum value of the composition (4) of a number (7)? How can I know the number of elements in it?

Answer 1

For numbers limited to $3$ you have the Tribonacci numbers, OEIS A000073, which begin $$ 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504,$$ and for numbers limited to $4$ you have the Tetranacci numbers, OEIS A00078 which begin $$ 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490,$$ Each number in the Tribonacci series is the sum of the previous three, because to get a composition of $n$ you can take a composition of $n-1$ and add a $1$, a composition of $n-2$ and add a $2$, or a composition of $n-3$ and add a $3$.

Answer 2

How can I know the number of elements in it?

Two-variable recurrence. If $a_m(n, k)$ is the number of compositions of $k$ numbers from $1$ to $m$ which total $n$ then $$a_m(n, k) = \begin{cases} 0 & \textrm{if } n < 0 \\ 1 & \textrm{if } n=0, k=0 \\ 0 & \textrm{if } n=0, k \neq 0 \\ \sum_{i=1}^m a_m(n-i, k-1) & \textrm{otherwise} \end{cases}$$

For practical computation, you would want to use dynamic programming.