3
$\begingroup$

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/

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

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!}\;.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.