# Permutations of $\{1,2,3,…,n\}$ where first k elements precede each other.

Number of permutations of $\{1,2,3,...,n\}$ where first $k$ elements have the property that element $1$ precedes element $2$ which precedes element $3$ ...... which precedes $k-1$ which precedes element $k$ (not necessarily immediately).

E.g: For $n = 7$ and $k = 3$, $(6152437) , (1243567)$, ... etc.

I tried like this: $n$ numbers can be permuted in $n!$ ways. The $k$ elements with preceding property can be permuted in $k!$ ways. But there is only one way satisfying the preceding property. So $n!/k!$ is the answer.

Is this correct? If so how could I write a more formal proof. Even though I verified for up to $n=6$ and $k=2,3$. I am still in doubt/

• Try with $n=4$ and $k=2$ to check if your answer is correct. – Morgan Rodgers Sep 1 '16 at 18:51

Your argument is correct. A slightly different way to say it is that there are $\binom{n}k$ ways to choose which positions in the permutation contain the numbers $1,\ldots,k$, whose order within those positions is fixed, and there are then $(n-k)!$ ways to arrange the remaining numbers in their positions. The total number of permutations satisfying the requirement is therefore
$$\binom{n}k(n-k)!=\frac{n!}{k!}\;.$$