My Math Forum Counting Problem

 Number Theory Number Theory Math Forum

 June 6th, 2012, 05:26 AM #1 Member   Joined: May 2012 Posts: 86 Thanks: 0 Counting Problem A number is said to be strictly ascendent when every one of its digits is greater than the one before it (For example: 2348, 123, 349, 258 159,etc.). How many strictly ascendent numbers are there between 1-10000? Help is appreciated.
 June 6th, 2012, 05:55 AM #2 Senior Member   Joined: Apr 2010 Posts: 215 Thanks: 0 Re: Counting Problem Write out all digits in increasing order: $123456789$ We need 4 digits, so scratch 5 of them ($\binom{9}{5}$ choices!), for example: $\not1 \not2 34\not5 \not6 78\not9$ $3478$ Now we have 2 choices per digit, whether to scratch it or not. But we can't scratch all of them so we have $2^4-1$ choices in total for each 4-digit number. So, the final answer is $\binom{9}{5} (2^4-1)=1890$ Edit: I think I might have counted some twice.
 June 6th, 2012, 06:36 AM #3 Member   Joined: May 2012 From: Chennai,India Posts: 67 Thanks: 0 Re: Counting Problem this seems to be a combinatorics problem... Valid digits are 1 5+4 5 6 7 8 9 If single digit nos can be counted as valid, then we have 9 numbers. For 12 to 89: If 1st digit is chosen as n, we have 9-n choices (the next high numbers) to fix the second digit. So , it is 8+7+6+5+4+3+2+1 = 8* 9/2 = 36 numbers For 123 to 789: If 1st and 2nd digit are fixed as 12, we have 7 choice to fill the 3rd digit. If 1st and 2nd digit are fixed as 13, we have 6 choice to fill the 3rd so, it is (7+6+5+4+3+2+1)+(6+5+4+3+2+1)+....(2+1)+1 = 84 numbers For 1234 to 6789: iF first 3 digits are fixed as 123, we have 6 choices to fill 4th digit If firlst 3 digits are fixed as 134, we have 5 choices So, it is (6+5+4+3+2+1)+(5+4+3+2+1)+---(2+1)+1= 56 numbers.. So we have totally 9+36+84+56 = 185 numbers. Any way to do this the number theory way?
June 6th, 2012, 08:17 AM   #4
Math Team

Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 408

Re: Counting Problem

Hello, Jakarta!

Quote:
 A number is said to be strictly ascendent when every one of its digits is greater than the one before it. (For example: 2348, 123, 349, 258 159, etc.) How many strictly ascendent numbers are there between 1-10000 ?

$\text{W\!e have the permutation: }\:1\,2\,3\,4\,5\,6\,7\,8\,9$

$\text{W\!e want numbers up to four digits.}$

$\text{W\!e can cross out 5, 6, or 7 of the digits.}$

[color=beige]. . [/color]$\begin{array}{cccccc}\text{Cross out 5 digits: } & \cancel1\,2\,\cancel3\,\cancel4\,5\,\cancel6\,\can cel7\,8\,9 & \text{ represents } & 2589 \\
\text{Cross out 6 digits: }& \cancel1\,\cancel2\,3\,\cancel4\,\cancel5\,\cancel 6\,7\,\cancel8\,9 & \text{ represents } & 379
\text{Cross out 7 digits: }& 1\,\cancel2\,\cancel3\,\cancel4\,\cancel5\,6\,\can cel7\,\cancel8\,\cancel9 & \text{ represents } & 16 \end{array}$

$\begin{array}{ccccccc}\text{2-digit numbers: }& {9\choose7} &=& \;36 \\ \\
\text{3-digit numbers: } & {9\choose6} &=& \;84 \\ \\
\text{4-digit numbers: } & {9\choose5} &=& 126 \\ \\ \hline
& \text{Total: } && 246 \end{array}$

June 6th, 2012, 08:23 AM   #5
Senior Member

Joined: Apr 2010

Posts: 215
Thanks: 0

Re: Counting Problem

Quote:
Originally Posted by soroban
Hello, Jakarta!

Quote:
 A number is said to be strictly ascendent when every one of its digits is greater than the one before it. (For example: 2348, 123, 349, 258 159, etc.) How many strictly ascendent numbers are there between 1-10000 ?

$\text{W\!e have the permutation: }\:1\,2\,3\,4\,5\,6\,7\,8\,9$

$\text{W\!e want numbers up to four digits.}$

$\text{W\!e can cross out 5, 6, or 7 of the digits.}$

[color=beige]. . [/color]$\begin{array}{cccccc}\text{Cross out 5 digits: } & \cancel1\,2\,\cancel3\,\cancel4\,5\,\cancel6\,\can cel7\,8\,9 & \text{ represents } & 2589 \\
\text{Cross out 6 digits: }& \cancel1\,\cancel2\,3\,\cancel4\,\cancel5\,\cancel 6\,7\,\cancel8\,9 & \text{ represents } & 379
\text{Cross out 7 digits: }& 1\,\cancel2\,\cancel3\,\cancel4\,\cancel5\,6\,\can cel7\,\cancel8\,\cancel9 & \text{ represents } & 16 \end{array}$

$\begin{array}{ccccccc}\text{2-digit numbers: }& {9\choose7} &=& \;36 \\ \\
\text{3-digit numbers: } & {9\choose6} &=& \;84 \\ \\
\text{4-digit numbers: } & {9\choose5} &=& 126 \\ \\ \hline
& \text{Total: } && 246 \end{array}$

That's nice but you forgot single digits.

 June 6th, 2012, 09:18 AM #6 Math Team   Joined: Dec 2006 From: Lexington, MA Posts: 3,267 Thanks: 408 Re: Counting Problem I didn't think one-digit numbers would be considered "strictly ascendent". Are the digits of "5" in increasing order?
June 7th, 2012, 04:05 AM   #7
Senior Member

Joined: Feb 2012

Posts: 144
Thanks: 16

Re: Counting Problem

Quote:
 Originally Posted by soroban Are the digits of "5" in increasing order?
I think they are. A number is not ascendent if there are two digits x1 x2 appearing in that order and with x2<=x1. You cannot find two such digits in 5.

 Tags counting, problem

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post superconduct Algebra 2 January 7th, 2014 10:01 AM zelmac Algebra 0 February 14th, 2013 05:29 AM scream Applied Math 2 February 21st, 2012 11:50 AM kec11494 Applied Math 1 December 20th, 2010 08:44 PM julian21 Applied Math 0 April 27th, 2010 09:48 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top