0
$\begingroup$

The task is to find the sum of all numbers (positive integers) that consist of at most $n$ digits, which sum up to $k$ (where $1 \leq k \leq 9$). For instance, if $n=2, k=3$, the desired sum equals $3 + 12 + 21 + 30 = 66$.

What I've come up with is the following, rather nasty recurrence ($a_{k, n}$ denotes the sum we are to find):

\[ \begin{split} & a_{k, 1} = k \\ &a_{k, n} = \sum_{i=0}^{k}i \cdot 10^{n-1} \cdot{n - 2 + k - i \choose n-2} + a_{k-i, n-1}. \end{split}\]

I obtained the latter formula by the following observation: the most significant digit in an $n$-digit number can be anything from $1$ to $k$. Each choice of such a digit $i$ contributes $i \cdot 10^{n-1}$, times the number of possible arrangements of digits at the less significant places, to the overall sum. There's ${(n-1) + (k-i) - 1 \choose k-i} = {n - 2 + k - i \choose n-2}$ such arrangements. Then (again, for each $i$), we must recursively include the contribution of "shorter" numbers ($n-1$), which meet our criterion $(k-i)$, to the sum. Finally, we count in the numbers whose length doesn't exceed $n-1$ (that's why the summation begins with $i = 0$).

This formula seems to work (I checked it for some small $n, k$). However, I've been aiming for a better solution - using such a recurrence for higher $n,k$ means an awful lot of computation. Is there a way to obtain a closed-form expression - by either simplifying my result or applying a completely different approach?

2 Answers 2

2

You have $k$ pebbles which you place into $n$ boxes. You start standing before the first box and do $k+n-1$ operations in arbitrary order until you stand with empty hands before the last box: either put a pebble in the box before you (do this $k$ times in total) or walk to the next box (do this $n-1$ times in total). You have $k+n-1\choose k$ ways to combine these steps. By interpreting the pebble counts per box as digits, each way uniquely determines an $n$-digit number (bacause fortunately $k\le9$) with digit sum $k$ (and possibly with leading zeroes). What you want is the sum of these $k+n-1\choose k$ different numbers. Since there is no difference between the boxes, you will put the same number of pebbles in each box on the average, that is each box has seen ${k+n-1\choose k}\cdot{k\over n}={k+n-1\choose k-1}$ pebbles. Therefore $a_{k,n} = {k+n-1\choose k-1}\cdot {10^n-1\over 9}$ where $10^n-1\over 9$ is the num,ber consisting of $n$ digits 1.

  • 0
    It's indeed much easier to consider this problem when we allow leading zeros (as both you and Ross Millikan imply) - I didn't think of that :) The combinatorial part is an ordinary combination with repetitions (exactly as in my attempt at solving this), but I didn't hit on the idea of the average sum of digits per significant place / the overall sum per place. Thanks for pointing this out!2012-09-05
0

It is easier if you allow leading zeros in your numbers. Then if you have a $n$ digit partition with all digits distinct, there are $n!$ numbers. Each digit is in each position $(n-1)!$ times, so the total is $k(n-1)!\frac{10^n}9$. If there are duplicates, this is reduced. You have to divide by the factorials of the numbers of duplicates.