Numbers with Non-Decreasing Digits

  • Context: Undergrad 
  • Thread starter Thread starter e(ho0n3
  • Start date Start date
  • Tags Tags
    Numbers
Click For Summary

Discussion Overview

The discussion revolves around the problem of counting n-digit numbers where the digits are non-decreasing and constrained by the condition that each digit a[i] must satisfy 1 ≤ a[i] ≤ i for i = 1, 2, ..., n. Participants explore various approaches to solve this problem, including transformations and patterns in the sequences generated.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant initially presents the problem and provides examples for n = 3.
  • Another participant points out a missing number in the initial examples, leading to clarification about the non-decreasing condition.
  • A participant suggests a transformation of the problem by fixing a[n] = n, proposing that this might simplify counting the solutions.
  • Some participants express confusion about the implications of the constraints and the nature of the sequences generated.
  • There is a discussion about the differences between adjacent terms in the sequences, with participants noting a lack of clear patterns.
  • One participant asserts that the answer relates to the nth Catalan number, though they acknowledge the difficulty in proving or deriving it.
  • Another participant proposes a formula involving series summation but questions its validity based on earlier examples.
  • Multiple participants engage in back-and-forth clarifications regarding the counts of valid sequences for various values of n.
  • There is a suggestion to explore patterns in the occurrence of digits beyond just the number of ones.
  • Some participants express uncertainty about the correctness of their proposed solutions and calculations.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best approach to solve the problem, and multiple competing views and interpretations of the constraints remain throughout the discussion.

Contextual Notes

Participants highlight various assumptions and conditions that affect the counting of valid sequences, including the requirement for non-decreasing digits and the specific bounds on each digit. The discussion reveals complexities in deriving a straightforward solution.

e(ho0n3
Messages
1,349
Reaction score
0
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?
 
Mathematics news on Phys.org
You missed 121.
 
Good point. Actually I forgot to mention the fact that a[1] ≤ a[2] ≤ ... ≤ a[n], i.e. the digits are non-decreasing.
 
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)
 
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...
 
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.
 
is it necessary that it should always start with 1?
can 2244 be a part of the sequence??

-- AI
 
TenaliRaman said:
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
 
duh! should've read the question more clearly ...

-- AI
 
  • #10
Hurkyl said:
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.
 
  • #11
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.
 
  • #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.
 
  • #13
What about with the list I gave?
 
  • #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...
 
  • #15
003
012
102
021
111

Do the digits in this list have any interesting properties? Any feature they all have in common?
 
  • #16
brilliant :

-- AI
 
  • #17
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
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 surprise!).
 
  • #19
e(ho0n3 said:
With n = 4, the solutions are

1111
1112
1122
1113
1123
1223
1133
1114
1124
1224
1134
1234
What about 1222 and 1233?
 
  • #20
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:
  • #21
chronon said:
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.
 
  • #22
e(ho0n3 said:
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.
 
  • #23
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)
 
  • #24
Do you believe 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 occurrence 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.
 
  • #25
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)
 
  • #26
Sorry, I was typing the reply when you posted yours, so i couldn't see it. You're right.
 
  • #27
Alkatran said:
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!}
 
  • #28
shmoe said:
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
 
  • #29
Alkatran said:
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?
 
  • #30
shmoe said:
So your t(n) is not counting the sequences you gave 3 posts back? The ones from the original question where a<=i?


my bad

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

Similar threads

High School Cool fact about number of digits in n!
  • · Replies 3 ·
Replies
3
Views
2K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Is dealing with large numbers as formula a thing? and how is it done?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Alternating Harmonic Numbers are cool, spread the word!
  • · Replies 4 ·
Replies
4
Views
4K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
3K
High School Number of palindromes made of n digits
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad What is the probability that the product of the digits is odd?
  • · Replies 13 ·
Replies
13
Views
3K
Undergrad Number of Integers (<N) divisible only by one power of 2
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Comparing ##a^b## and ##b^a##
  • · Replies 19 ·
Replies
19
Views
2K
Graduate Is this Recursive Pattern in the Collatz Sequence Known?
  • · Replies 3 ·
Replies
3
Views
2K