• 0
bonanova

Digits on the rise

Question

What do 15 489 1256 and 24578 have in common?

They are positive integers whose digits are strictly increasing left to right.

How many of them are there?

0

Share this post


Link to post
Share on other sites

7 answers to this question

  • 0

First group it by number of digits (so group 1 will be 1 digit, group 2 will be 2 digits, etc). Then each group will be the functional equivalent of asking, "what are the possible combinatorics for n numbers?" where n is the group number. The reason for this is that any combination of (non-repeating) digits can be ordered from lowest to greatest, and the combination function (nCr) basically takes this into account (as opposed to a permutation, in which the order of items creates unique possibilities). So the final solution will be

SUM (from n=1 to n=9) of 9Cn

=511

0

Share this post


Link to post
Share on other sites
  • 0

Please clarify if you mean

  1. how many positive increasing-digit integers in {the set of all possible digit combinations in the stated problem} or
  2. how many positive increasing-digit integers in {the set of all positive integers}

(I have a feeling it's the latter option...)

Edited by Dariusray
0

Share this post


Link to post
Share on other sites
  • 0

Correct. The latter: positive integers whose digits are strictly increasing left to right.

0

Share this post


Link to post
Share on other sites
  • 0

First, my thinking about some restrictions for the strictly-increasing-digit integers:


*No numbers may have a zero digit (beginning zeroes disappear and any other position of zero ruins the strictly-increasing pattern)
*No single-digit integers (not technically a digit increase)
*The highest integer with [n] digits must start with [10-n] digit (highest 2-digit number must start with 8 and highest 9-digit number must start with 1)

Now, a brute-force count (2-digit number starting with 8, plus those starting with 7, etc.) for 2-digit and 3-digit permutations revealed a pattern that a number with [n] digits will need [10-n] addends to result in the total count of permutations...

Once I began the first few addends in my brute-force count for 4-digit permutations, I saw that aligning the addends revealed a vertical pattern that increased my new addends by the counts I had for my previous [n]-digit permutations. (This pattern is much easier for me to visualize than to explain)...

Once I saw the two patterns, I found it much easier to compute with far less brute force (I wish I could make a grid here for alignment):

2-digit integers==>(1+2+3+4+5+6+7+8+9) permutations==> 45 valid integers
3-digit integers==>(1+3+6+10+15+21+28) permutations==>84 valid integers [saw horiz. pattern here; # of addends decreased to 7]
4-digit integers==>(1+4+9+16+25+36) permutations==>91 valid integers [saw vert. pattern here; # of addends decreased to 6 and values increased by 3, then 6, then 10, etc. from counts directly above]
5-digit integers==>(1+5+13+25+41) permutations==>85 valid permutations [now 5 addends & increases of 1, 4, 9, etc. from counts directly above]
6-digit integers==>(1+6+18+38) permutation==>63 valid permutations [continuing horiz. & vert. patterns from here]
7-digit integers==>(1+7+24) permutations==>32 valid permutations
8-digit integers==>(1+8) permutations==>9 valid permutations
9-digit integers==>(1) valid permutation

TOTAL strictly-increasing-digit integers possible==>(45+84+91+85+63+32+9+1)==>410

Provided my patterned computations are accurate, I believe there are 410 valid integers
0

Share this post


Link to post
Share on other sites
  • 0
There's an even simpler observation that immediately gives the correct answer.
0

Share this post


Link to post
Share on other sites
  • 0

There's an even simpler observation that immediately gives the correct answer.

I assumed there is,

2

9-1
, but I'm not sure right now why that is.
0

Share this post


Link to post
Share on other sites
  • 0

There's an even simpler observation that immediately gives the correct answer.

I assumed there is,

2

9-1
, but I'm not sure right now why that is.

The power set (the set of all subsets) of a set of n objects has size 2n. For 9 digits, n=9. Then subtract off the empty set.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.