Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

Your construction works with the following interpretation:

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.