Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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! –  Quintofron Sep 5 '12 at 17:32

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.