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.
 
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Back
Top