Numbers with Non-Decreasing Digits

[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] ≤ 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?

[Hurkyl]

You missed 121.

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

[Hurkyl]

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)

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

[Hurkyl]

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.

[TenaliRaman]

is it necessary that it should always start with 1?
can 2244 be a part of the sequence??

-- AI

[Gokul43201]

is it necessary that it should always start with 1?
can 2244 be a part of the sequence??

-- AI

No Tenali,

That would violate a[i] <= i

[TenaliRaman]

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

-- AI

[e(ho0n3]

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.
I don't see where you're going with this. It seems very trivial.

[Hurkyl]

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.

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

[Hurkyl]

What about with the list I gave?

[e(ho0n3]

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

[Hurkyl]

003
012
102
021
111

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

[TenaliRaman]

brilliant :surprised:

-- AI

[Hurkyl]

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.

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

[chronon]

With n = 4, the solutions are

1111
1112
1122
1113
1123
1223
1133
1114
1124
1224
1134
1234What about 1222 and 1233?

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

[e(ho0n3]

What about 1222 and 1233?

Yes I forgot those. Thank you.

Alkatran: You have the numbers wrong. The left-most digit can be at most 1. The second left-most digit can be at most 2. And so on.

Hurkyl & shmoe: I'll look into the pattern more closely. Thanks.

[Alkatran]

Yes I forgot those. Thank you.

Alkatran: You have the numbers wrong. The left-most digit can be at most 1. The second left-most digit can be at most 2. And so on.

Hurkyl & shmoe: I'll look into the pattern more closely. Thanks.

Oh. One minute then. :grumpy:

[Alkatran]

n=1: 1 solution () increment
1
n=2: 2 solutions 3*1-1 = 2
11
12
n=3: 5 solutions 3*2-1 = (3 + 2)
111
112
113
122
123
n=4: 14 solutions 3*5-1 = (4 + 3 + 2) + (3 + 2)
1111
1112
1113
1114
1122
1123
1124
1133
1134
1222
1223
1224
1233
1234
n=5: 42 solutions 3*14 (not -1?) = ((5 + 4 + 3 + 2) + (4 + 3 + 2) + (3 + 2)) + ((4 + 3 + 2) + (3 + 2)) = (5+2)/2*(5-1) + (4 + 2)/2*(4-1) + (3 + 2)/2*(3-1)
11111
11112
11113
11114
11115
11122
11123
11124
11125
11133
11134
11135
11144
11145
11222
11223
11224
11225
11233
11234
11235
11244
11245
11333
11334
11335
11344
11345
12222
12223
12224
12225
12233
12234
12235
12244
12245
12333
12334
12335
12344
12345

t(n) = t(n-1) + (n+2)/2 * (n-1)

[ZeAsYn51]

Do you beleive that there is a pattern here? I think that it's a good step forward to use subtraction of the terms in their order to help find the pattern, if one exists. Also, are you only looking for a pattern in the occurance of ones. Maybe you could try looking for a pattern in the other numbers and wherever one of these doesn't fall, there is a one.

[Alkatran]

I put what I think is the pattern in my last post.

You can simplify it to 1/2x^2+1/2x-1

Then you can use a series summing formula on that... (I don't remember the formula for ^2, so I can't do it)

[ZeAsYn51]

Sorry, I was typing the reply when you posted yours, so i couldn't see it. You're right.

[shmoe]

I put what I think is the pattern in my last post.

You can simplify it to 1/2x^2+1/2x-1

Then you can use a series summing formula on that... (I don't remember the formula for ^2, so I can't do it)

I don't see how this pattern works, if t(1)=1 your formula says t(2)=t(1)+(2+2)/2*(2-1)=3, when it should be 2.

As already stated earlier, this generates the Catalan numbers, (2n)!/{(n+1)!*n!}

[Alkatran]

I don't see how this pattern works, if t(1)=1 your formula says t(2)=t(1)+(2+2)/2*(2-1)=3, when it should be 2.

As already stated earlier, this generates the Catalan numbers, (2n)!/{(n+1)!*n!}

No, it shoud be 3. There are 3 answers:
11
12
22

[shmoe]

No, it shoud be 3. There are 3 answers:
11
12
22

So your t(n) is not counting the sequences you gave 3 posts back? The ones from the original question where a[i]<=i?

[Alkatran]

So your t(n) is not counting the sequences you gave 3 posts back? The ones from the original question where a[i]<=i?

my bad

...maybe it won't work for the next value then

[nino]

Let be K(n)=all the numbers obtained with the conditions of your problem.
***If n=1 then k(n)=1
1

***If n=2 then k(n)=3
11
12

22

***If n=3 then k(n)=10
111
112
113
122
123
133

222
223
233

333

***If n=4 then k(n)=35
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

It is easy to see that k(n)= S(1<=i<=n) [S(1<=j<=i) of {T(sub_i)(sub_j)}]
where T(sub_i)(sub_j) is the j-th triangular number and S represents a sumatoria (to add up)

Note: I hope you can understand me, I dont speak and write english very well.

[nino]

Let be the matrix A=

[ \ t1 t2 t3 t4 ... t(n-3) t(n-2) t(n-1) tn ]
[ t1 \ t2 t3 t4 ... t(n-3) t(n-2) t(n-1) tn ]
[ t1 t2 \ t3 t4 ... t(n-3) t(n-2) t(n-1) tn ]
[ t1 t2 t3 \ t4 ... t(n-3) t(n-2) t(n-1) tn ]
[ t1 t2 t3 t4 \ ... t(n-3) t(n-2) t(n-1) tn ]
[ t1 t2 t3 t4 ... \ t(n-3) t(n-2) t(n-1) tn ]
[ t1 t2 t3 t4 ... t(n-3) \ t(n-2) t(n-1) tn ]
[ t1 t2 t3 t4 ... t(n-3) t(n-2) \ t(n-1) tn ]
[ t1 t2 t3 t4 ... t(n-3) t(n-2) t(n-1) \ tn ]
[ t1 t2 t3 t4 ... t(n-3) t(n-2) t(n-1) tn \ ]

where tn stands the n-th triangular number. Then, the number you are looking for is the sum of all the t(n's) under the line.

[Gokul43201]

nino, you're missing the condition that a[i]<=i. So, the first digit can not be larger than 1...