1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ I don't know how it will work out, but try posting at math.stackexchange.com/questions?sort=newest $\endgroup$
    – Will Jagy
    Jul 28, 2011 at 4:04
  • 1
    $\begingroup$ 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? $\endgroup$
    – David Roberts
    Jul 28, 2011 at 4:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – S. Carnahan
    Jul 28, 2011 at 4:30
  • $\begingroup$ 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. $\endgroup$ Jul 28, 2011 at 5:20
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 28, 2011 at 5:23

0

Browse other questions tagged or ask your own question.