Given positive interger N, now many non-decreasing sequences of length

AI Thread Summary
The discussion focuses on counting non-decreasing sequences of length N with entries less than N, confirming that the entries are positive integers. It establishes a bijection between two sets: A, the set of non-decreasing sequences, and B, the set of non-negative integer sequences with a specific sum. The relationship allows for counting the elements in set B using the formula binom(2N-2, N), which simplifies the problem. However, one participant notes that the growth rate of the resulting sequences is too rapid for their needs. The exploration highlights an effective combinatorial approach to the problem.
Dragonfall
Messages
1,023
Reaction score
5
Given positive interger N, now many non-decreasing sequences of length N are there whose entries are less than N?
 
Mathematics news on Phys.org


are the entries positive integers?
 
Yes .
 


This isn't in the homework section so I'm assuming it isn't homework.

Let A be the set of sequences of the type in the post.
Let B be the set of sequences of N+1 non-negative integers with sum N-2.
A and B are in bijection by associating a sequence a_1,a_2, \ldots ,a_N of A to b_1,b_2,\ldots,b_{N+1} defined by b_i = a_i - a_{i-1} where we let a_0 = 1, a_{N+1}=N. The inverse is given by associating a sequence b_1,b_2,\ldots,b_{N+1} of B to a_1,\ldots,a_N defined by a_{i+1} = a_{i}+b_{i+1} where we let a_0 = 1.

Thus we can just count B which has
\binom{(N+1)+(N-2)-1}{(N+1)-1} = \binom{2N-2}{N}
elements.
 


Wow I would never have thought of that. Thanks. Unfortunately it grows too fast for my purposes.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top