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.
 A: 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.
A: 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

