# How many numbers between $100$ and $900$ have sum of their digits equal to $15$?

How many numbers between $100$ and $900$ have sum of their digits equal to $15$?

I was wondering if we could derive any direct combinatoric formula to solve problem like this,my strategy is kind of trying all permutation for $100$ to $200$ then $200$ to $300$ then ...,and finally summing them up to get $62$ (if I there is not mistake)though this may not be very difficult to solve using this approach (as we are dealing with $3$ digits numbers with individual digits not greater than $9$)but is this also the fastest/efficient one?

-
@Thijs Laarhoven:Yes you are right,but I am not getting,how could we solve that equations with that constraints? – Quixotic Sep 20 '11 at 0:55
There was a mistake in the original formulation. You should be solving $x_1 + x_2 + x_3 = 15$ with $0 \leq x_i \leq 9$, $x_1 \neq 0$ but also $x_1 \neq 9$ (as solutions above $900$ are not allowed). – TMM Sep 20 '11 at 1:22
(I apologize if I am the reason everyone made this oversight of not allowing $x_1 = 9$. My bad!) – TMM Sep 20 '11 at 1:24
My fastest solution would be to open a spreadsheet, make column A with the numbers 100 to 900, columns B-D with the various digits (tens by mod(int(a*/10),10), add them up, and if(E*=15,1,0) in column F, add column F. – Ross Millikan Feb 23 '12 at 5:20

This problem can be reduced to solving

$$x_1 + x_2 + x_3 = 15, \quad 0 \leq x_i \leq 9, \quad x_1 \neq 0, \quad x_1 \neq 9$$

First, we solve

$$x_1 + x_2 + x_3 = 15, \quad 0 \leq x_i \leq 15$$

This is a standard stars and bars problem, with solution $\binom{15+3-1}{15} = 136$. Now which solutions are wrong? Well, first of all those with one of them above $10$. But if, say, $x_1 \geq 10$, then we can write $x_1' = x_1 - 10$ and $x_2' = x_2, x_3' = x_3$ to reduce the problem to

$$x_1' + x_2' + x_3' = 5, \quad 0 \leq x_i' \leq 5$$

This is again a standard stars and bars problem, with solution $\binom{5+3-1}{5} = 21$. Since exactly one of $x_1,x_2,x_3$ could be above $10$, this gives $3 \cdot 21 = 63$ wrong solutions in total. So there are $136 - 63 = 73$ solutions to

$$x_1 + x_2 + x_3 = 15, \quad 0 \leq x_i \leq 9$$

Finally, we need to subtract $4$ solutions with $x_1 = 0$ (i.e. $(x_2,x_3) \in {(6,9),(7,8),(8,7),(9,6)}$), but also subtract $7$ solutions for $x_1 = 9$ (i.e. $(x_2,x_3) \in {(0,6),\ldots,(6,0)}$). This gives $62$ solutions in total.

-
+1,This is a beautiful explanation!,even for the last two counting we could use the same approach as explained in before paragraphs,It seems I understood it completely now.Thanks a lot :) – Quixotic Sep 20 '11 at 2:42
@Fool: Very true. The numbers $4$ and $7$ come from solving $$x_2 + x_3 = 15, \quad 0 \leq x_i \leq 9$$ and $$x_2 + x_3 = 6, \quad 0 \leq x_i \leq 6$$ respectively, so we're actually solving two more stars and bars problems here. (Three actually, as for the first you have to do a split again of $0 \leq x_i \leq 15$ and subtracting the wrong solutions. For the first you get $\binom{15+2-1}{15} - 2 \cdot \binom{5+2-1}{5} = 4$ and for the second you get $\binom{6+2-1}{6} = 7$.) – TMM Sep 20 '11 at 13:22

This is almost a standard stars-and-bars (or marbles and boxes) problem. You have $15$ marbles, and you want to distribute them amongst $3$ boxes (the digits) in such a way that the first box gets at least one marble and at most $8$ marbles and each of the other two boxes gets at most $9$ marbles. ($900$ is the only allowable $3$-digit number beginning with $9$, and its digits don’t sum to $15$, so it can be ignored.) Equivalently, you’re looking for non-negative integer solutions to $x_1+x_2+x_3=15$ subject to the constraints $1\le x_1 \le 8, x_2,x_3 \le 9$.

After putting one marble in the first box, you’ve $14$ left to distribute. Ignoring the upper bounds, this can be done in $\dbinom{14+3-1}{3-1}=\dbinom{16}{2}=120$ ways. The ways that have at least $9$ marbles in the first box are bad, so they have to be subtracted off. After putting $9$ marbles in the first box, you’ve $6$ left to distribute; this can be done in $\dbinom{6+3-1}{3-1}=\dbinom{8}{2}=28$ ways. Similarly, there are $\dbinom{4+3-1}{3-1}=\dbinom{6}{2}=15$ distributions that have too many marbles in the second box (because after putting one in the first box and $10$ in the second box you’ve only $4$ left to distribute) and $15$ that have too many in the third box. It’s not possible to have too many marbles in two boxes: that would require at least $19$ marbles. Thus, the final count is $120-28-2(15)=62$ numbers between $100$ and $900$ whose digits sum to $15$.

-
But brute-force says the answer is $62$?! – Quixotic Sep 20 '11 at 1:12
@FoolForMath: You’re right: in the last step I carelessly forgot that I still had to put one marble in the first box. I’ve corrected it now. – Brian M. Scott Sep 20 '11 at 1:22

HINT:

$x_1 + x_2 + x_3 = 15, \; x_1 \geq 1, \; x_1, x_2, x_3 < 10$ is very relevant here.

-
I can see this before,but what I am not getting how to solve this equations with those constraints? – Quixotic Sep 20 '11 at 0:58
What constraint prevents you from being able to solve it? – mixedmath Sep 20 '11 at 0:59
$x_1 \geq 1, \; x_1, x_2, x_3 \leq 10$ – Quixotic Sep 20 '11 at 1:00
There are many solutions... start cranking some out! – The Chaz 2.0 Sep 20 '11 at 1:00
@Fool: those are $all$ the constraints. Are you saying you can't handle either the lower or the upper bounds separately? – mixedmath Sep 20 '11 at 1:04

There is a high mass:volume ratio, so here we go ...

I'll just get you started counting, since other answers are being posted.
$15 = 9 + 6 + 0$. How many permutations of this are between $100$ and $900$?

$15 = 9 + 5 + 1$. How many ...?

$15 = 9 + 4 + 2$...

...

$15 = 8 + 7 + 0$

...

$15 = 7 + 7 + 1$...

-
I prefer (and +1 to) Brian's answer; this is more for support and/or getting started. – The Chaz 2.0 Sep 20 '11 at 1:12

I wrote a simple brute force test for this:

[Test]
public void GivenNumbersBetween100And900_WhenCalculatingItsNumbers_ThenPrintThoseWhoEqual15()
{
var counter = 0;
for (var hundredth = 1; hundredth <= 9; hundredth++)
{
for (var tenth = 0; tenth <= 9; tenth++)
{
for (var singles = 0; singles <= 9; singles++)
{
if (hundredth + tenth + singles == 15 && 100*hundredth + 10*tenth + singles <= 900)
{
counter++;
Console.WriteLine("{0:D3}: {1}{2}{3}", counter, hundredth, tenth, singles);
}
}
}
}
Assert.That(counter, Is.EqualTo(62));
}


And the result is:

001: 159
002: 168
003: 177
004: 186
005: 195
006: 249
007: 258
008: 267
009: 276
010: 285
011: 294
012: 339
013: 348
014: 357
015: 366
016: 375
017: 384
018: 393
019: 429
020: 438
021: 447
022: 456
023: 465
024: 474
025: 483
026: 492
027: 519
028: 528
029: 537
030: 546
031: 555
032: 564
033: 573
034: 582
035: 591
036: 609
037: 618
038: 627
039: 636
040: 645
041: 654
042: 663
043: 672
044: 681
045: 690
046: 708
047: 717
048: 726
049: 735
050: 744
051: 753
052: 762
053: 771
054: 780
055: 807
056: 816
057: 825
058: 834
059: 843
060: 852
061: 861
062: 870

-