   SEARCH HOME Math Central Quandaries & Queries  Question from Sky, a student: Hi I'm a Student and i'll try my best to state the problem perfectly. The number of non-decreasing sequences of size at least 1 and at most N, such that each element of the sequence lies between L and R, both inclusive. Eg:- N=1 L=4 R=5 ans= 2. [{4},{5}] N=3 L=4 R=6 ans= 19. [{4},{5},{6},{4,4},{4,5},{4,6},{5,5},{5,6},{6,6} {4,4,4},{4,4,5},{4,4,6},{4,5,5},{4,5,6},{4,6,6},{5,5,5},{5,5,6},{5,6,6} ,{6,6,6}] Consider two simplifications:

The number of non-decreasing sequences of size at least 1 and at most N,
such that each element of the sequence lies between L and R, both inclusive.

=

The number of non-decreasing sequences of size at least 1 and at most N,
such that each element of the sequence lies between 1 and (R-L)+1, both
inclusive.

=

(The number of non-decreasing sequences of size EXACTLY N,
such that each element of the sequence lies between 0 and (R-L)+1, both
inclusive.) - 1

The first simplification is because you can then add (L-1) to every
term of the sequence to get a sequence with terms between L and R.

The second simplification is that if a sequence starts with 0, you
can remove all the 0s to get a shorter sequence (or pad a shorter
sequence with 0s at the beginning to get size exactly N).

The next step is to get rid of the ordering: If you get a bunch of N
numbers between 0 and (R-L)+1, there is only one way to order them to
make a non-decreasing sequence. So you only need to figure out in how
many ways can you get a bunch of N numbers between 0 and (R-L)+1.

Let X(0) be the numbers of zeros in the bunch, X(1) the number of ones,
and so on up to X(R-L+1). Since there are N numbers in all, you get the
equation
X(0) + X(1) + ... + X(R-L+1) = N,
and the question is now how many solutions are there to this equation,
with X(0), X(1), ..., X(R-L+1) being nonnegative integers.

To figure it out, it is best to represent the numbers by sticks:
1 is |, 2 is ||, 3 is |||, ..., and 0 is no sticks. Look at sums
represented this way:
1 + 2 + 3 is |+||+|||
1 + 4 + 1 is |+||||+|
4 + 0 + 2 is ||||++||
...

Each sum corresponds to an permutation of sticks and plus signs.
The number of sticks is the value of the sum, in your case N.
The number of plus signs is one less that the number of terms
in the sum, in your case R-L+1. So the number of solutions
of the equations above is the number of ways to permute
N identical sticks and R-L+1 identical plus signs: (N+R-L+1)!/N!(R-L+1)!.
You subtract one from that to get the number of your sequences.

Claude      Math Central is supported by the University of Regina and the Imperial Oil Foundation.