# Count the number of group $(x_1;x_2;x_3;…x_c)$

How many groups $(x_1;x_2;x_3;...x_c)$ satisfy that: $$\begin{cases} x_i \in \{1;2;...;m\} \ \forall i \\ x_2 \le x_3 \le x_4 \le ... \le x_c \\ x_2 < x_1 \end{cases}$$ With m,c $\in N (m>c)$

-
Perhaps you mean sequence, and not group? "Group" has a very specific meaning. –  Thomas Andrews Nov 8 '12 at 14:36
Are you sure you want to have $x_2<x_1$ here, rather than the seemingly more natural requirement $x_1<x_2$? Because if it's $x_2<x_1$ then $x_2$ can be anywhere to the right of $x_1$, independently of where the other $x_k$ are. Either one of these wouldn't be difficult to count. But which one do you mean, in your question? –  coffeemath Nov 8 '12 at 18:33
I thinks the group that means "Set" –  LevanDokite Nov 9 '12 at 1:36
@coffeemath it 's true –  LevanDokite Nov 9 '12 at 1:36

For $2 \le k \le c-1$ define $y_k=x_{k+1}-x_k$ and also define $y_c=m-x_c$.

Then your condition $x_2 \le x_3 \le ... \le x_c \le m$ becomes the restriction that each $y_k \ge 0$ for $2 \le k \le c.$

Note that I put in the last inequality $x_c \le m$ since in the statement of the problem each $x_i$ is taken from $\{ 1,2,...,m\}.$

Now you also want $x_2 <x_1$, so for fixed $x_2$ there are $m-x_2$ choices for the value of $x_1$ as an integer greater than $x_2$ but not greater than $m$.

Note also that for fixed $x_2$ we have [1] $$y_2+y_3+...+y_c=m-x_2,$$ and conversely any solution to this equation in nonnegative $y_k$ will lead back to one of the sequences of $x_j$ you wish to count, and the correspondence is one-to-one. So we need only sum over each possible value of $x_2$ of the number of solutions to [1], each multiplied by the number $(m-x_2)$ of choices for where $x_1$ is to lie to the right of $x_2$.

This gives the total to be

$$\sum_{x_2=1}^{m-1} (m-x_2) C(m-x_2+c-2,c-2)$$ where the term $C(m-x_2+c-2,c-2)$ is the binomial coefficient giving the number of solutions of equation [1] in nonnegative integers. [This last application of a binomial coefficient to count number of solutions in nonnegative integers is fairly well known.]

EDIT: The above formula involves a summation over $x_2$ going from 1 to $m-1$. The OP has asked for a simpler answer; here I think all one can do is get rid of the need for a summation. This summation can be done in closed form, and one can get another formula for the final count which does not involve a summation. This formula is as follows: $$(c-1)C(m+c-2,c),$$ where as before $C(n,k)$ denotes the binomial coefficient $n$ choose $k$.

I highly doubt this answer can be somehow re-written without binomial coefficients at all, since such a rewrite would entail some "new" way to express binomial coefficients by a simple algebraic formula.

ADDED NOTE: The formula above can be shown directly from the problem, without first summing and then going to the closed form. The OP has requested I include this explanation:

Let $N(m,r)$ denote the number of sequences $u_k$ with $$1 \le u_1 \le ... \le u_r \le m.$$

Note that this last inequality is equivalent to the following strict inequality: $$1\le u_1 < u_2+1 < u_3+2 < ... < u_r+r-1 \le m+r-1.$$ The number of solutions to the latter is the number of $r$ element subsets of $\{1,2,...,m+r-1\}$, so that we have $$N(m,r)=C(m+r-1,r),$$ where $C(n,k)$ is the binomail coefficient.

Let $H(m,c)$ denote the number of solutions to the inequality system consisting of $1 \le x_2 \le ... \le x_c \le m$ along with $1 \le x_1<x_2$. Then $$H(m,c)+N(m,c)=m \cdot N(m,c-1),$$

since the right side counts the cases where $x_1$ can be any nimber from 1 to $m$ and the two numbers $H(m,c)$ and $N(m,c)$ are the counts of disjoint sets of choices for the $x_k$ which together make up the number counted by the right side.

We therefore have a somewhat simple formula for $H(m,c)$, namely $$H(m,c)=m \cdot C(m+c-2,c-1) - C(m+c-1,c).$$ We can simplify this result to $(c-1)C(m+c-2)$ on using the values of binomials in terms of factorials, and some algebra.

That is, we take $$\frac{m(m+c-2)!}{(c-1)!(m-1)!}-\frac{(m-c-1)!}{c!(m-1)!}$$ and factor out $$C(m+c-2,c)=\frac{(m+c-2)!}{c!(m-2)!}.$$ This gives the other factor as $$\frac{mc}{(m-1)}-\frac{m+c-1}{m-1}=\frac{(m-1)(c-1)}{m-1}=c-1.$$

So the final simplified form of the required count $H(m,c)$ is $$H(m,c)=(c-1) \cdot C(m+c-2,2).$$

-
I don't except this result $$\sum_{x_2=1}^{m-1} (m-x_2) C(m-x_2+c-2,c-2)$$ I need shorter result –  LevanDokite Nov 13 '12 at 6:55
ok i accept, I have the same result with you but not sastisfied with it much –  LevanDokite Nov 14 '12 at 5:18
LevanDokite: If you're interested, I have a simple proof of the formula $(c-1)binomial(m+c-2,c)$ for the problem, without first summing and then afterwards getting the sum into closed form. It's based only on the count of nonnegative sums, applied twice, and manipulating two binomial expressions into one. If you want to see that, I can add it at the end of the answer I gave. –  coffeemath Nov 14 '12 at 5:45
thanks you so much, please give me the answer at the end of the answer you gave –  LevanDokite Nov 14 '12 at 10:55
LevanDokite: I have inserted the explanation at the end of the answer. –  coffeemath Nov 15 '12 at 20:47