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.

  • #31
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 don't speak and write english very well.
 
Mathematics news on Phys.org
  • #32
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.
 
  • #33
nino, you're missing the condition that a<=i. So, the first digit can not be larger than 1...
 

Similar threads

High School Cool fact about number of digits in n!
  • · 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
3K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
2K
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
Graduate Is this Recursive Pattern in the Collatz Sequence Known?
  • · Replies 3 ·
Replies
3
Views
1K
Graduate 10-adic number proof: A^10 has the same n+1 last digits as 1
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Preventing specific cases of digital signature forgery and repudiation
  • · Replies 14 ·
Replies
14
Views
2K