# Limit the maximum value of the composition of an integer

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?

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$$.
• The last justifies the recurrence. If I have a composition of $13$ and are limited to $3$, consider the last digit. If it is $1$, you have a composition of $12$ left when you erase the $1$, so the number of ways to get $13$ is the sum of the ways to get $10, 11,$ and $12$ because you can append the appropriate digit at the end. Yes, if you had a key with $5$ characters you would have each number the sum of the preceding $5$ for the same reason. – Ross Millikan Dec 30 '18 at 19:07
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}$$