Given $N$ numbers, how many ways can we arrange those numbers such that they are Strictly increasing or decreasing.
For eg – $N=2$ we have $1,2$ so possible rearrangements are-
{{1,2} , {2,1}}
Can someone help me out ?
EDIT : The given answer is for non-strictly but it would be great if I have the answer converted to its special case when it's strictly increasing or decreasing.
Best Answer
This answer is for the original version of the question before the author changed the question.
An example: Let's just look at nondecreasing sequences. To deal with nonincreasing sequences, the approach is the same (and to deal with them together, you need to subtract the number of constant sequences).
You have the set $\{1,2,3\}$. Let $x_1$ be the number of $1$'s, $x_2$ be the number of $2$'s and $x_3$ be the number of $3$'s. Once the counts of $1$, $2$, and $3$ are known, the increasing and decreasing sequences are known.
Since the sequences must be of length $3$, you're considering the problem of finding $x_1\geq 0$, $x_2\geq 0$, and $x_3\geq 0$ such that $x_1+x_2+x_3=3$. This is a standard formulation of the stars-and-bars problem. The number of such combinations is $$ \binom{3+3-1}{3}=\binom{5}{3}=10. $$ We can check this with \begin{align*} (1,1,1) && (1,1,2) && (1,1,3)\\ (1,2,2) && (1,2,3) && (1,3,3)\\ (2,2,2) && (2,2,3) && (2,3,3)\\ (3,3,3). \end{align*}
In this case, the total is $2\binom{5}{3}-3=17$ ways to be nonincreasing or nondecreasing. (10 sequences that are nonincreasing, 10 sequences that are nondecreasing, and 3 sequences that are both nonincreasing and nondecreasing - the constant ones).
In general, the formula should be $$ \binom{2N-1}{N}-N. $$