Tagged: combinatorics

NonStrictly Increasing Sequences

What is the number of nonstrictly increasing sequences of M integer numbers between 1 and N?

Let xi be the number of times the number “i” appears in the sequence.
So, We need to find the number of solutions for the equation
x1+x2+x3+…+xN = M where xi>=0
And That is ((M+N1) choose (N1)).

That’s true, but how do you calculate the number of solutions of x1+x2+… +xN=M?

Usually the standard explanation goes like this : Consider for example , X1+X2+X3=5. The solution can be considered equivalent to 5 *s separated by 2 s . For example (1,2,2) corresponds to ***** . In the general case, M *s and N1 s and that gives ((M+N1) choose (N1))

That’s right:) Alternatively (or more like equivalently), you can add 1 to the second smallest element, 2 to the third smallest element, and so on, and reduce the problem to choosing M different numbers from 1 to N + M – 1.

Log in to reply.