Number of non-decreasing sequences How do I find the number of non-decreasing sequences of length $N$, such that all number in the sequences lie in the range $[a, b]$.
Also, the frequency of the most frequently occurring element should be unique.
For example, 1 1 2 3 is a valid sequence, but 1 1 2 2 3 is not a valid sequence, because the frequency of 1 and 2 is the same in the $2$nd sequence.
 A: The maximum frequency, say $k$, for a sequence can range from $1$ to
$N$. We will count the number of valid sequences for a fixed $k$
then sum  over $k = 1, ... ,N$.
Let $d = b - a$.
The number, say $c$, having (uniquely) the maximum frequency $k$ can
be any number from $a$ to $b$. So we will fix $c$, count the number
of sequences for it, then subsequently sum over $c = a,...,b$, which
in fact is a simple multiplication by $d+1$ since the number of
sequences is the same for each $c$.
If number $c$ occurs exactly $k$ times then there are $N-k$ numbers
from $a$ to $b$, excluding $c$, in the sequence such that none of
them occurs $k$ or more times.
It is the same as putting $N-k$ balls into $d$ cells, with no cell
containing $k$ or more balls.
Let $S_k$ be the set of all arrangements, without the
$k$-restriction on the cells, of $N-k$ balls in $d$ cells.
$\vert S_k \vert = \binom{N-k+d-1}{d-1}\qquad\mbox{using the common
"stars and bars" argument.}$
For $i = 1,...,d$ let set $S_{ki} = \left\{s \in S_k :\mbox{
arrangement $s$ has at least $k$ balls in the $i^{th}$
cell}\right\}$
We seek the cardinality of set:
$V_k =
\left(\bigcup_{i=1}^{d}{S_{ki}}\right)^c\qquad\left(\mbox{where the
complement is wrt $S_k$}\right)$ this set $V_k$ being that of valid
sequences for fixed $k$ and $c$.
By the Inclusion-Exclusion Principle:
\begin{eqnarray*}
\vert V_k \vert &=& \vert S_k \vert - \sum_{i=1}^{d}{\vert S_{ki}
\vert} + \sum_{i<j}{\vert S_{ki} \cap S_{kj} \vert} - ... -
\left(-1\right)^{i+1} \vert \bigcap_{i=1}^{d}{S_{ki}} \vert
\end{eqnarray*}
\begin{eqnarray*}
\vert S_{ki} \vert &=& \mbox{No. of ways to put $N-2k$ balls into $b-a$ cells} \\
&&\qquad\left(\mbox{since we have at lease $k$ balls in the $i^{th}$ cell}\right) \\
&=& \binom{N-2k+d-1}{d-1}
\end{eqnarray*}
and generally, for an intersection of $n$ of the $S_{ki}$ sets,
\begin{eqnarray*}
\vert \bigcap_{j=1}^{n}{S_{ki_j}} \vert &=&
\binom{N-\left(n+1\right)k+d-1}{d-1}.
\end{eqnarray*}
Thus,
\begin{eqnarray*}
\vert V_k \vert &=& \vert S_k \vert -
\sum_{n=1}^{d}{\left(-1\right)^{n+1}\binom{d}{n}
\binom{N-\left(n+1\right)k+d-1}{d-1}} \\
\vert V_k \vert &=& \sum_{n=0}^{d}{\left(-1\right)^n\binom{d}{n}
\binom{N-\left(n+1\right)k+d-1}{d-1}}
\end{eqnarray*}
Summing over $c = a,...,b$ and over $k = 1,...,N$ gives the final
result:
\begin{eqnarray*}
Ans. &=& \left(d+1\right) \sum_{k=1}^{N}{\vert V_k \vert} \\
&=& \left(d+1\right) \sum_{k=1}^{N}{\left[ \sum_{n=0}^{d}{\left(-1\right)^n \binom{d}{n} \binom{N-\left(n+1\right)k+d-1}{d-1}}\right]}. \\
\end{eqnarray*}

As an example, let $\left[a,b\right] = \left[1,4\right]$ and $N =
3$. So $d = 3$.
There are $16$ valid sequences:
\begin{eqnarray*}
111, 112, 113, 114, 122, 133, 144, \\
222, 223, 224, 233, 244, \\
333, 334, 344, \\
444.
\end{eqnarray*}
\begin{eqnarray*}
Ans. &=& 4 \sum_{k=1}^{3}{\left[ \sum_{n=0}^{3}{\left(-1\right)^n
\binom{3}{n} \binom{5-\left(n+1\right)k}{2}}\right]}
\\ &=& 4 \sum_{k=1}^{3}{\left[ \binom{5-k}{2} -
3 \binom{5-2k}{2} + 3 \binom{5-3k}{2} - \binom{5-4k}{2}\right]}
\\ &=& 4 \left[ \binom{4}{2} -
3 \binom{3}{2} + 3 \binom{2}{2}\right] + 4 \left[
\binom{3}{2}\right] + 4 \left[ \binom{2}{2}\right] \\
&=& 4\left(6 - 9 + 3\right) + 4\left(3\right) + 4\left(1\right) \\
&=& 16
\end{eqnarray*}
A: Presumably the sequences are made of integers, and $a,b$ are integers.
You probably already know that the number of non-decreasing sequences is $\tbinom{N+b-a}{N}$ because there is a one-to-one relationship with binary sequences of the form $++XX+X+...++X+$ where $X$ represents the placement of a number, and $+$ represents the increment of the number to place, starting from $a$.
What we want to do now is to count binary sequences in which the longest run of $X$s is unique. One method is to construct sequences in which the longest run of $X$s has length below $r$, then insert a run of length $r$.
Let $f(x,y,z)$ be the number of compositions of $x$ into $y$ non-zero parts such that the longest part is less than $z$. Consider those sequences in which there are $r$ runs of $X$s (including the longest), for a total of $N$, and the longest run is of length $L$. The number of such sequences, $g(r,L)$, equals:
$$g(r,L)=f(N-L,r-1,L)\cdot r\cdot (2f(b-a,r,\infty)+f(b-a,r+1,\infty))$$
where the first factor breaks up the $X$s into runs, the second factor places the longest run, and the third factor arranges the $+$s around the runs of $X$s in three different ways: $+X+X+X,\ X+X+X+,$ or $+X+X+X+$.
So the answer we seek can be expressed as $\sum_{r,L} g(r,L)$ summing over all plausible values of $r$ and $L$.
All that remains is to determine how to find $f(x,y,z)$. It shouldn't be too hard to see that $f(x,y,\infty)=\tbinom{x-1}{y-1}$. Now for $f(x,y,z)$, we use inclusion-exclusion. We subtract cases in which one part is forced to be at least $z$. Then add back cases in which two parts are forced to be at least $z$, etc. This gives $$f(x,y,z)=\sum_{k=0}^{\lfloor x/z\rfloor} (-1)^k\tbinom{y}{k}\tbinom{x-1-k(z-1)}{y-1}$$
