# Numbers with Non-Decreasing Digits

1. Oct 10, 2004

### e(ho0n3

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. Oct 10, 2004

### Hurkyl

Staff Emeritus
You missed 121.

3. Oct 10, 2004

### e(ho0n3

Good point. Actually I forgot to mention the fact that a[1] ≤ a[2] ≤ ... ≤ a[n], i.e. the digits are non-decreasing.

4. Oct 10, 2004

### Hurkyl

Staff Emeritus
Ok that makes it more interesting!

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

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)

5. Oct 10, 2004

### e(ho0n3

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...

6. Oct 10, 2004

### Hurkyl

Staff Emeritus
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.

7. Oct 11, 2004

### TenaliRaman

can 2244 be a part of the sequence??

-- AI

8. Oct 11, 2004

### Gokul43201

Staff Emeritus
No Tenali,

That would violate a <= i

9. Oct 11, 2004

### TenaliRaman

duh!! should've read the question more clearly ....

-- AI

10. Oct 11, 2004

### e(ho0n3

I don't see where you're going with this. It seems very trivial.

11. Oct 12, 2004

### Hurkyl

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

(more detail in white)

12. Oct 12, 2004

### e(ho0n3

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.

13. Oct 12, 2004

### Hurkyl

Staff Emeritus
What about with the list I gave?

14. Oct 13, 2004

### e(ho0n3

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...

15. Oct 13, 2004

### Hurkyl

Staff Emeritus
Do the digits in this list have any interesting properties? Any feature they all have in common?

16. Oct 13, 2004

### TenaliRaman

brilliant :surprised:

-- AI

17. Oct 13, 2004

### Hurkyl

Staff Emeritus
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.

18. Oct 14, 2004

### shmoe

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!).

19. Oct 14, 2004

### chronon

20. Oct 14, 2004

### Alkatran

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