Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Numbers with Non-Decreasing Digits

  1. Oct 10, 2004 #1
    I've been unable to solve the following problem for a while know: How many n-digit numbers a[1]a[2]...a[n] exits where 1 ≤ a ≤ i for i = 1, 2, ..., n? For example, with n = 3 there are five numbers:
    111
    112
    122
    113
    123

    I was trying to look at the pattern of 1's being generated but to not avail. Is there a simpler way of looking at this problem?
     
  2. jcsd
  3. Oct 10, 2004 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You missed 121.
     
  4. Oct 10, 2004 #3
    Good point. Actually I forgot to mention the fact that a[1] ≤ a[2] ≤ ... ≤ a[n], i.e. the digits are non-decreasing.
     
  5. Oct 10, 2004 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ok that makes it more interesting!

    The trick is to restate the problem that is easier to count. :smile:

    I'll get you started: require that a[n] = n, so if n = 4 then your solutions are:

    1114
    1124
    1224
    1134
    1234

    Note that solutions of this new problem correspond exactly to solutions of your problem (but with different n). I assert that it's easier to count using my version of the problem! (It will require another transformation before it becomes trivial, though)
     
  6. Oct 10, 2004 #5
    I'm confused. Maybe I didn't state the problem correctly. With n = 4, the solutions are

    1111
    1112
    1122
    1113
    1123
    1223
    1133
    1114
    1124
    1224
    1134
    1234

    Not so trivial anymore...
     
  7. Oct 10, 2004 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    My problem requires that a[n] = n. The solutions for n = 5 in my problem will simply be the solutions for n = 4 in your problem, but with a 5 appended to the end.
     
  8. Oct 11, 2004 #7
    is it necessary that it should always start with 1?
    can 2244 be a part of the sequence??

    -- AI
     
  9. Oct 11, 2004 #8

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    No Tenali,

    That would violate a <= i
     
  10. Oct 11, 2004 #9
    duh!! should've read the question more clearly ....

    -- AI
     
  11. Oct 11, 2004 #10
    I don't see where you're going with this. It seems very trivial.
     
  12. Oct 12, 2004 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For the next transformation, you want to look at something different than a sequence of nondecreasing numbers...

    (more detail in white)

    Look at the differences between adjacent terms instead.
     
  13. Oct 12, 2004 #12
    Why are the details in white? For the list I gave with n = 3, the difference in adjecent terms is:

    00, 01, 10, 02, 11

    Nothing interesting there. For the list I gave with n = 4, the difference in adjecent terms is:

    000
    001
    010
    002
    011
    101
    020
    003
    012
    102
    021
    111

    I don't see any pattern here either.
     
  14. Oct 12, 2004 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What about with the list I gave?
     
  15. Oct 13, 2004 #14
    For your list, it is

    003
    012
    102
    021
    111

    This is not really insightful at all. By the way, the answer to my question is the nth Catalan number, not that anybody can prove or derive it though...
     
  16. Oct 13, 2004 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Do the digits in this list have any interesting properties? Any feature they all have in common?
     
  17. Oct 13, 2004 #16
    brilliant :surprised:

    -- AI
     
  18. Oct 13, 2004 #17

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Hrm, actually I overlooked something... while I think this form is much simpler to analyze than the original problem, it's not as easy as I originally thought.
     
  19. Oct 14, 2004 #18

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    What do you know about Catalan numbers? It might be easier to relate this problem back to something familiar about Catalan numbers that you know how to prove.

    I'm thinking of the "mountains with n up steps and n down steps" formulation of Catalan numbers. To show the number of these mountains is equivalent to the number of your sequences you'll want to look at the differences between consequetive digits as Hurkyl described (no big suprise!).
     
  20. Oct 14, 2004 #19
    What about 1222 and 1233?
     
  21. Oct 14, 2004 #20

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    Let's say & means !, except with + instead of *
    I'm sure there's some symbol for this but I don't know it.
    But, (x&)& means to apply that & for every value from x to 1. IE:
    3& = 3 + 2 + 1
    3&& = 3& + 2& + 1& = (3 + 2 + 1) + (2 + 1) + 1

    n=1: 1 solution (0+1) increment
    1
    n=2: 3 solutions (2+1) = 2&
    11
    12
    22
    n=3: 10 solutions ((3+2+1) + (2+1) + 1) = 3&&
    111
    112
    113
    122
    123
    133
    222
    223
    233
    333
    n=4: 34 [([4+3+2+1]+[3+2+1]+[2+1]+1) + ([3+2+1]+[2+1]+1) + ([2+1]+1) + 1] = 4&&&
    1111
    1112
    1113
    1114
    1122
    1123
    1124
    1133
    1134
    1144
    1222
    1223
    1224
    1233
    1234
    1244
    1333
    1334
    1344
    1444
    2222
    2223
    2224
    2233
    2234
    2244
    2333
    2334
    2344
    2444
    3333
    3334
    3344
    3444
    4444

    Very complicated. Series of series of series.
    I'll go ahead and say that for any n, the value of possibilities is n&^n
    If you understand what I mean by that.
     
    Last edited: Oct 14, 2004
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Numbers with Non-Decreasing Digits
  1. 4 digit number (Replies: 4)

Loading...