Another way to express choosing $k$ objects from $n$

Question

Suppose $(x_1,...,x_k)$ is a vector such that each $x_i$ is positive $ {\bf integer} $ and $1 \leq x_i \leq n$. I am trying to understand why the number of such vectors that satisfy $x_1 < x_2 < ... < x_k$ is ${n \choose k}$. In my notes it says it is obvious, but I am having difficulty seeing why is such. Let's for simplicity take $k=2$ so we want to verify

that vectors $(x_1,x_2)$ such that $x_1 < x_2$ are ${n \choose 2}$. Let us see. Notice that if we consider all possible Pairs in $n$ by $n$ array we have half of them that satisfy requirement but without $n/2$ elements (half of diagonal). So we have

$$ n^2/2 - n/2 = \dfrac{n^2 - n }{2} = \dfrac{n (n-1) }{2} = {n \choose 2}$$

So this seems to agree. However, if we consider higher values of $k$, the argument becomes cumbersome. Can someone provide with an insight to be able to see this type of combinatorics arguments?

Answer 1

Take the set of integers $\{1, \dots, n\}$. Choose $k$ of these and arrange them in increasing order $x_1, \dots, x_k$. Then we have $x_1 < \dots < x_k$. Clearly, this process covers all of the possible vectors of this kind, so there are $n \choose k$ ways of constructing such a vector.

The reason $n \choose k$ works here is because we are counting without considering order (since the order in which we choose the $x_i$ doesn’t matter) and we are not allowed repetitions (since we have the strong inequality $<$ rather than $\leq$).

Answer 2

Such increasing vectors $(x_1,\dots,x_k)$ are in one-to-one correspondence with subsets of size $k$ as follows. Given $k$-vector $(x_1,\dots,x_k)$, the $k$-subset is $\{x_1,\dots,x_k\}$. Given $k$-subset $\{x_1,\dots,x_k\}$, the $k$-vector is $(x_1,\dots,x_k)$. If the $<$ were instead $\le$, you would no longer have this trivial correspondence.