# Alternative combinatorial proof

I have a question with regards to combinatorics. Here is the following question:

Find the number of ordered $c$-tuples $(n_1,n_2,\cdots,n_c)$ such that $n_1,n_2,\cdots,n_c\in\{1,2,\cdots,m\}$ where $m$ is a positive integer, and $n_1>n_2$, and $n_2\leq n_3\leq\cdots\leq n_c$.

The way I did it is as such: Let the value of $n_2$ be $k$ where $k\in\{1,2,\cdots,m-1\}$. Then there are $m-k$ possible values of $n_1$. Also, the number of possible values of $(n_3,n_4,\cdots,n_c)$ is equal to the number of $(c-2)$-element multi-subsets of the multi-set $\{\infty\cdot k,\infty\cdot (k+1),\cdots,\infty\cdot m\}$, which is equal to $\binom{m-k+c-2}{c-2}$. Hence, the required answer is equal to \begin{eqnarray*} \sum_{k=1}^{m-1}(m-k)\binom{m-k+c-2}{c-2} &=&\sum_{k=1}^{m-1}(c-1)\binom{m-k+c-2}{c-1}\\ &=&(c-1)\sum_{k=1}^{m-1}\binom{m-k+c-2}{c-1}\\ &=&(c-1)\binom{c-2+m}{c}. \end{eqnarray*}

The last answer suggests (somewhat) that the question could possibly be approached in another manner. Currently, I am thinking of another approach to this question, where I was thinking of the following: First permute $c$ a's and $m-2$ b's, for which there are $\binom{c-2+m}{c}$ ways, then slot a $c$ so that it is in between some 2 a's, and it is of the form $\cdots acbbbbb\cdots a\cdots$, which there are $(c-1)$ ways. However, I have trouble showing that such a construction would result in a bijection.

Is there any way to prove/disprove whether such a construction would result in a bijection? Also, I would like to know if there are also other possible approaches to this problem that would give a more direct proof to this problem.

-

Begin with $X=1,j=2$. Read the sequence you made. Whenever you see $b$ or $c$, increase $X$ by one. Whenever you see $a$, set $n_j=X$ and increase $j$ by one. Whenever you see $cbb\cdots b a$, instead the $a$ sets $n_1$.
You should be able to easily work out what the sequence of $a,b,c$ must be given the $n_k$, which shows this is a bijection.