How do you find the number of unique integer sequences of a nondecreasing sequences length $n$ with these conditions?
$$ a_{n+1} \geq a_{n}$$
Possible rephrasing: Given a particular nondecreasing sequence of length $n$ $\{a_1,a_2, \ldots,a_n\}$, how many nondecreasing sequences $\{b_1,b_2, \ldots ,b_n\}$ are there in which $b_i \leq a_i$ for $1 \leq i \leq n$?
The sequence is sorted low to high and the next number is same or higher.
[1,2,3,4,5] or [1,1,2,2,5] or [5,5,5,5,5]
The permutations must be lower than the sequence, but same or higher than the number before it.
For [1,2,3,4,5] there are 42 unique combinations.
1,1,1,1,1
1,1,1,1,2
1,1,2,2,5
1,1,3,4,5
1,2,3,4,5
1,1,3,2,4 - no because 2 is less than 3
1,3,3,4,5 - no because 3 is greater than 2 in 1,*2*,3,4,5
For 5,5,5,5,5 there are 126 unique sequences.
1,1,1,1,1
1,2,3,4,5
5,5,5,5,5
Brute force counting looks like
for a = 1 to 5
for b = a to 5
for c = b to 5
for d = c to 5
for e = d to 5
count++
print a,b,c,d,e
For [5] the count is 5.
For [1,5] or [1,1,1,1,5] the count is 5.
For [5 repeating n times]
n count
1 5
2 15
3 35
4 70
5 126
6 210
7 330
8 495
9 715
10 1001
I tried summation of summation of summation. $n(n+1)(n+2)(n+3)/2*3*4$
3 summations counts sequences length 5 and limits are $n,n,n,n,n$. 4 summations counts 6. 5 summations counts 7.
I don’t know how to subtract sequences if the limits are $1,2,3,4,5$.
how do you get $\frac{10!}{5!6!} = 42$ from $1,2,3,4,5$ and $\frac{9!}{4!5!} = 126$ from $5,5,5,5,5$?
Answering this question in general is probably just too difficult, so I'll just restate the problem into a maybe more understandable form. If you arrange $a_1$ squares in a first row, then $a_2$ squares in a second row (left aligned), and so on until a last row of $a_n$ squares, the you have an upside-down version of the Young diagram for the partition $(a_n,\ldots,a_2,a_1)$. What you are looking for is the number of ways to remove some boxes from the ends of these rows, so that the remainder is still an upside-down Young diagram. The actual question also requires that the first column is entirely retained (since it implicitly discriminates against $0$), but you can obtain that by chopping off the first column from the Young diagram; I will assume this is done so that we are now allowed to remove all boxes from certain rows if we like. Then the number is equal to the number of lattice paths from top-left to bottom right across the Young diagram, staying within its bounds.
The number of such paths is a known number in certain cases. When the Young diagram is a rectangle of sides $k$ and $l$, then the number is the binomial coefficient $\binom{k+l}k$ (our lattice path has $k$ horizontal and $l$ vertical steps, which can be intermixed in any way). If the Young diagram is an equilateral triangle shape with $n$ squares on a side, the number is the Catalan number $C_{n+1}$ (extending the paths with an initial vertical edge and a final horizontal edge, one gets a lattice paths of length $2(n+1)$ staying to one side of a diagonal line, counting of which is one of the interpretations of that Catalan number).