0
$\begingroup$

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)$

  • 0
    @coffeemath it 's true2012-11-09

1 Answers 1

1

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 , 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. 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).$

  • 0
    LevanDokite: I have inserted the explanation at the end of the answer.2012-11-15