Number of ways to take $k$ out of $n$ (1 to $n$) numbers and arrange them in order

Question

How many ways are there to take $k$ out of $n$ numbers ($1$ to $n$) and arrange them in order?

Example: $n=4$, $k=2$:

$12, 13, 14$

$23, 24$

$34$

I tried to find an answer on SE but all I got were questions about $k$ consecutive out of $n$ numbers. I only need them to be in order. Sorry if that question has been asked already.

Thank you so much

Answer 1

What you're looking for is called the binomial coefficient. Let's start from the basics, and look at what the binomial coefficient is, in a combinatoric sense:

For $k,n\in\mathbb N$, the binomial coefficient is defined as:

$$\binom{n}{k} :=\left|\binom{\{1,...,n\}}{k}\right|$$ where

$$\binom{\{1,...,n\}}{k} := \{A\in\{1,...,n\}\mid |A|=k\} $$

In other words, the binomial coefficient precisely counts the amount of $k$-element sets you can make from the set $\{1,...,n\}$.

Now, why is it that the amount of unordered sets equals the amount of sets, if we impose an order on them?

Let's look at one set, e.g. $\{1,2,3\}$. Using this set, we can create the following permutations: $$ [1,2,3] ; [1,3,2] ; [2,1,3] ; [2,3,1] ; [3,1,2] ; [3,2,1] $$ Each of these permutations however is nothing but our set, on which we additionally imposed an order. For our first case, $[1,2,3]$, the order would be the regular ascending order - i.e. $1<2<3$, and it's easy to see, that this order is only true for the first case, and for none of the others we listed there (i.e. $2>1$ in $[2,1,3]$).

Generally we have, that if we impose on a set a total order, there is precisely one permutation of this set which fulfills the order.

To finish this in the good, combinatorial fashion we now show that there exists a bijection between the binomial coefficient $\binom{\{1,...,n\}}{2} $ and $ \{(x,y)\in\{1,...,n\}^2\mid x<y\}$, the set of all ordered pairs with two elements.

For this we create the function
$$\phi:\binom{\{1,...,n\}}{2} \to \{(x,y)\in\{1,...,n\}^2\mid x<y\} \\ \{a,b\}\mapsto (\min(a,b),\max(a,b)) $$

We can show that this function is a bijection in multiple ways. The cleanest is to show that it is injective and surjective. So let's take a look:

The function is surjective, as for any $(a,b)\in \{(x,y)\in\{1,...,n\}^2\mid x<y\}$ we can find a set $A\in \binom{\{1,...,n\}}{2}$, namely the set $\{a,b\}$.

The function is injective, as if we'd have two tuples $\{a_1,b_1\},\{a_2,b_2\}\in \binom{\{1,...,n\}}{2}$ with $$ \phi(\{a_1,b_1\})=\phi(\{a_2,b_2\}) $$ we'd know that their minimum and maximum are equal, i.e. $$\min(a_1,b_1) =\min(a_2,b_2) \\ \land\\ \max(a_1,b_1) =\max(a_2,b_2)$$

As we have though that $a_1\neq b_1 \land a_2\neq b_2$ (this follows from the forms of the sets in $\binom{\{1,...,n\}}{2}$), this already means that the both sets $\{a_1,b_1\},\{a_2,b_2\}$ are identical (they have the same lower, and the same higher element, and they have exactly two elements, and the higher and lower element aren't identical).

Therefore $\phi$ is bijective, and thus $$\left|\{(x,y)\in\{1,...,n\}^2\mid x<y\}\right|= \left|\binom{\{1,...,n\}}{2}\right| = \binom{n}{2} $$

Answer 2

Hint: Given $k$ distinct numbers, there is only one way to order them, so all you need is the number of ways of choosing $k$ numbers from $n$.

Answer 3

You have $n$ choices for the first, $n-1$ choices for the second, $n-2$ for the third, on until $n-k+1$ for the last. Then $$n(n-1)(n-2)\ldots(n-k+1)=\frac {n!}{(n-k)!}$$ For the edited question, there are $${n \choose k}=\frac {n!}{k!(n-k)!}$$ ways to choose $k$ items out of $n$. The above version has a factor $k!$ because it can put them in any order. See Wikipedia on combinations.

Answer 4

This is the number of $k$-combinations out of a set of $n$ elements, then it's up to you to order these $k$ elements, so the number sought for is simply $$ \binom nk =\frac{n!}{k!(n-k)!}. $$