Weak Composition with Restrictions(0..9)

I want to optimise some subtask and I'm not good enough in math.
Given: There are ticket numbers with $k$ digits from 0 to 9. Let $n$ is sum of digits for the ticket number.
Needed: calculate count for all possible $n$ from 0 to $9*k$. I can do it with brute force with $O(10^k)$, but I want do better.
When $n < 10$, this is Weak Composition with pretty simple formula with good $O(n, k)$, so I easily obtained counts for first ten $n$.
Starting from $n=10$, this is Weak Composition with Restrictions and I didn't manage to obtain formula from the few related SO posts.
Exactly, I need help with recursive/iterative formula $count(n, k)$ for $n$ from 10 to $(9*k)/2$ (due to gaussian distribution)
Typical $k$ is small: 4,6,8.

Your name suggests that you can read Russian. If so, you can look these articles. In particluar, in the second paper is provided a recurrent formula for $count(n,k)=N_k(n)$ in their notation (they swap $n$ and $k$):

$$N_k(n)=\sum_{l=0}^9 N_{k-1}(n-l),$$

where if $n<9$ then $N_{k-1}(n-l)=0$ for $l>n$;

and a table for $N_k(n)$ for $k\le 4$.

I’m going to relook these papers for additional results.

• 10 answers out from 10! Thanks a lot! I've added some notes in answer form for non-mathematicians, who will face with the same problem. Aug 14 '17 at 12:41

The bounty does wonders! Alex Ravsky's answer is exact thing I was looking for. All hail "Kvant" magazine № 12, 1976 year! :)

Formula allows me to calculate all $N_k(n)$ where $n$ is from $0$ to $9K / 2$ and k is const like $K = 4, 5, 6, etc$. Values for $n$ from $9K / 2 + 1$ to $9K$ is mirror of the first half. It seems, the formula is the fastest way to do this due to small loops amount and $+ -$ operations only.

Only thing I want to add is my coding improvements:
Memoization. Formula is extremely suited for it:

• it takes very small memory amount - $O((9K/2+1)*K)$
• hit ratio - 100%
• it reduces calculations a lot - for $K=6$ only $168$ ones are new out from total $1203$

k=1 precalculation. Using memoization allows us to precalculate $N_1(n)$ and avoid formula branch for $k=1$.

$\sum$ optimization. $l > n$ case is contiguous, so just changing upper bound from $9$ to $min(n, 9)$ allows us to avoid unnecessary loops with $l > n$ checkings:

$$N_k(n)=\sum_{l=0}^{min(n,9)} N_{k-1}(n-l)$$

Below is Ruby example:

# N_k(n)
def f(n, k, memo)
memo[n][k-1] ||=
(0..[n, 9].min).reduce(0){ |sum, l| sum + f(n-l, k-1, memo) }
end

K = 4
median = 9 * K / 2

memo = Array.new(median + 1) { Array.new(K) }
memo.each_with_index{ |a, n| a[0] = n > 9 ? 0 : 1 } # k==1 precalculation

puts (0..median).map{ |n| f(n, K, memo) }.join(' ')


Output:

1 4 10 20 35 56 84 120 165 220 282 348 415 480 540 592 633 660 670

• Thanks for your kind words. The referenced papers contains also other interesting formulae for $N_k(n)$, which I was going to add to my answer, but yesterday my computer unexpectedly died, so I urgently had to assemble another from handy stuff. :-) Aug 14 '17 at 13:08
• Disclaimer: I am not a bounty hunter, although my profile suggests the opposite. :-) It happened because the easiest way for me to find an interesting, hard and unanswered question is to look at featured questions. :-) Aug 14 '17 at 13:08
• Haha, my SO strategy is same for getting interesting and hard question! Aug 14 '17 at 14:18

Small examples, where the number at array index $i$ tells you how many $k$-digit numbers have digit sum $i$:

k = 0: [1]
k = 1: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
k = 2: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
k = 3: [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55, 45, 36, 28, 21, 15, 10, 6, 3, 1]
k = 4: [1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 282, 348, 415, 480, 540, 592, 633, 660, 670, 660, 633, 592, 540, 480, 415, 348, 282, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1]


For example for $k=4$, the digit sums $0$, $1$ and $2$ appear in $1$, $4$ and $10$ numbers, respectively.

How to get from the $k$ array to the $k+1$ array? Well, that means using one more digit. How many numbers have a certain digit sum $i$ now? If the added digit is $3$, then the earlier $k$ digits must sum to $i-3$. So look up in the $k$ array how many $k$-digit numbers have digit sum $i-3$. Same for the other $9$ digit options. And then just add up those ten possibilities. So if we call the array $f$, you get $f_{k+1}[i] = \sum_{d=0}^9 f_k[i-d]$ (Where out-of-bounds indexes hold value $0$).

A Ruby implementation/demo:

k = 4
p k.times.reduce([1]) { |f| ([0] * 9 + f + [0] * 9).each_cons(10).map(&:sum) }


Output:

[1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 282, 348, 415, 480, 540, 592, 633, 660, 670, 660, 633, 592, 540, 480, 415, 348, 282, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1]


Note the left added [0] * 9 emulate the out-of-bounds zeros mentioned above and the right added [0] * 9 initialize the new higher digit sums we can reach with the new digit.