1

With how many ways can we choose the integers $x_1,x_2, \dots , x_k$ such that the condition $1 \leq x_1<x_2< \dots <x_k \leq n$ is satisfied?

Do I have to find $(y_1,y_2, \dots,y_k):y_1+.....+y_k=\dots$ such that an other condition is satisfied?

evinda
  • 7,823

2 Answers2

2

The answer is $\binom{n}{k}$.

Suppose you picked them ignoring the order. Then there is clearly only one order in which they are all decreasing. So for every unordered set there is a unique ordered set that Works and visce-versa.

Asinomás
  • 105,651
  • I haven't understood it..Could you explain it further to me?? – evinda Apr 25 '14 at 21:11
  • The number of ways to select them in a decreasing order is the same as the number of ways to select them ignoring the order. Since for every unordered selection of numbers there is only one way to put them in order that satisfies $x_1<x_2<\dots x_n$. – Asinomás Apr 25 '14 at 21:34
  • In other words if you allready know the set of numbers selected, there is only one way to assign $x_1,x_2.\dots x_n$ – Asinomás Apr 25 '14 at 21:35
2

There is a much easier way to solve the problem, but we can use $y_i$ as you suggest.

Let $y_1=x_1$, $y_2=x_2-x_1$, $y_3=x_3-x_2$, and so on up to $y_k=x_k-x_{k-1}$. Finally, let $y_{k+1}=(n+1)-x_k$. The $y_i$ add up to $n+1$, and every solution of $y_1+y_2+\cdots+y_{k+1}=n+1$ in positive integers corresponds to a valid choice of the $x_i$.

André Nicolas
  • 507,029
  • So can we choose the integers with $$\binom{n+1+k+1-1}{n+1-1}=\binom{n+k+1}{n}=\binom{n+k+1}{k+1}$$ ways?? – evinda Apr 25 '14 at 21:10
  • 1
    This is the case "every kid gets at least $1$ candy" of Stars and Bars. We are looking for positive solutions. The number is $\binom{n+1-1}{k+1-1}=\binom{n}{k}$. But there is, as shown by another solution, a much simpler way of seeing this. – André Nicolas Apr 25 '14 at 21:30
  • Don't we have to set $y_1=x_1-1$ ? shouldn't it be $y_i \geq 0, \forall i$ ? – evinda Apr 26 '14 at 11:23
  • And also why do we have to take till $y_{k+1}$ and not till $y_k$? – evinda Apr 26 '14 at 11:25
  • Both my end-choices were made to have the condition on all the $y_i$ be $y_i\ge 1$. The $y_{k+1}$ was to take care of the condition that $x_k\le n$. If I chose $y_1=x_1-1$ the condition on $y_1$ would be it is $\ge 0$, not $\ge 1$. There are other ways of doing it, that you may have seen, in which we let $z_1=x_1-1$, and then $z_k=x_{k}-x_{k-1}-1$. If we do it that way, our conditions on the $z_i$ are that they are $\ge 0$. – André Nicolas Apr 26 '14 at 11:39