How Many Numbers Problem

[AuSmith]

How many 5 digit numbers have their digits strictly increasing? Like 12589 and 24569.

How many 5 digit numbers have their digits just increasing? Like, now you include numbers like 11455 and 23368.

[stupidityismygam]

[bradp]

This is much more arduous explanation...

#1 - for 2 digit numbers... it would be 8 + 7 + 6 + ... 1 = 36 (8th triang number!)
for 3 digit numbers...
1xx = 7 + 6 + 5 + ... 1 = 28
2xx = 6 + 5 + ... = 21
3xx = 5 + 4 ... = 15
4xx = 10
5xx = 6
6xx = 3
7xx = 1

28 + 21 + 15 + 10 + 6 + 3 + 1 = 84 (sum of first 7 triangular numbers !

4 digit
12xx + 13xx + 14xx + 15xx + 16xx + 17xx = (using above) = 56 (sum of first 6 triang numbers)
23xx + 24xx + 25xx + 26xx + 27xx = 35 (sum of 5
34xx + 35xx + 36xx + 37xx = 20 (sum of first 4)
4xxx ... = sum of first 3 = 10
5xxx... = sum of first 2 = 4
6xxx = 6789 = 1

56 + 35 + 20 + 10 + 4 + 1 = 126 (sum of the sums of the first 1,2,3,4,5,6 triang numbers ??)

so:
2 digits: 8th triang number
3 digits: sum of 1st 7 triang numbers
4 digits: sum of sums of 1 triang number, 2 triang numbers ... 6 triang numbers
following the pattern
5 digits: sum of sums of sums of 5 triang numbers (bad wording, i know)


1
1+4
1+4+10
1+4+10+20
1+4+10+20+35
= 5*1 + 4*4 + 10*3 + 20*2 + 35*1 = 126? same as 4 digit numbers w/ increasing digits... Strange, although as the number of digits gets higher there will be less and less numbers like that until 9 digit numbers w/ only 1: 123456789

6 digit numbers like that would then be:
1
1+5
1+5+15
1+5+15+35
= 84
7 digit numbers
1
1+6
1+6+21
= 36
8 digit numbers
1
1+7
= 9
9 digit numbers: 1

[stupidityismygam]

does anybody need me to explain my solution better (b/c it is much quicker than the triangular number way)

edit: it simplifies to, 9 C n where n is the number of digits

for n digits there are 9 P n ways to form a number with n distinct digits (excluding 0)


then you get the n! because out of every n factorial there is only 1 possible strictly increasing number
so it would be (9 P n)/(n!) or 9 C n

[AuSmith]

Okay, [unparseable or potentially dangerous latex formula]... but the main question was the second one. Have you thought about it?

[fht]

Aaron, do you mean to include numbers like 11112, 12222, and 11111?
Best Wishes

[AuSmith]

Yes, as long as there is no decrease when running through the digits.

[catalyst]

(9+5-1)C5 ?

Every number is 1:1 with some combination of **_***_ _*_ _*, which in this case corresponds to 366778, i think.

So in general, for an n digit number, there are (8+n)Cn numbers of the form 112236, where they are increasing...

[AuSmith]

Okay, that's what I got.