Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Every now and then I get interested in trying to find a discussion on the combinatorial problem of how many numbers of n digits or less has a digit sum less than m

namely $\left|\left\{k\in\mathbb{Z}| 0\le k < 10^n\, and\,\, f(n)\le m \right\} \right|$ where $f(k) = \sum_{i=0}^\infty k_j$ given that $k_j\in\mathbb{Z}$ satisfy $k = \sum_{i=0}^\infty k_j10^j$ and $0 \le k_j \le 9$.

It's easy to see this is just the number or integral co-ordinates contained with in a particular corner of an n-dimensional hybercube so it will involve the mixture of sums of consecutives to some power. But I believe this simplifies in some way.

I seem to recall that there's a solution of to this problem in the form of $\sum_{j=0}^n g(j)$ where g is some closed form expression and n is the number of dimensions/digits. But what I'm hoping to find is a discussion of this problem and approaches to solving it.

Any direction you can recommend is most appreciated. Preferably an online discussion.

Many thanks

share|improve this question

closed as off topic by Gjergji Zaimi, Will Jagy, Gerry Myerson, Douglas Zare, Ryan Budney Jul 28 '11 at 8:40

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

    
I don't know how it will work out, but try posting at math.stackexchange.com/questions?sort=newest –  Will Jagy Jul 28 '11 at 4:04
1  
Just to point out (and you may know this) MO is not designed for discussions. And what is wrong with a paper that discusses the problem, when compared to an online discussion? Would you be happy with answers that pointed you to publications? –  David Roberts Jul 28 '11 at 4:05
1  
If $m$ is more than 9, then you are no longer restricted to a corner of the $n$-cube $[0,9]^n$. It would be better to say that you are counting the lattice points in the intersection of $[0,9]^n$ and the half-space that is bounded by the hyperplane $\sum_{i=1}^n k_i = m$ and contains the origin. –  S. Carnahan Jul 28 '11 at 4:30
    
It's easy to count this if you have no upper bound on the digits. Use inclusion-exclusion on the number of digits $10$ or greater. –  Douglas Zare Jul 28 '11 at 5:20
1  
I think you'll find discussions of this type of problem in any introductory discrete math textbook, in the chapter on inclusion-exclusion and/or in the chapter on generating functions. Voting to close. –  Gerry Myerson Jul 28 '11 at 5:23