5
$\begingroup$

Let $\{1...n\}$ and $k$, a number between $1\le k \le n$. How many permutations are there for the set, where $k$ is smaller than all the number to it's right.

My thought:
We have to place $k$ at the cell number $k$.
Then, we have $(k-1)!$ permutations for the smaller numbers and $(n-k)!$ for the greater numbers. All in all, we have: $(k-1)!(n-k)!$

Somehow, the right answer is: $$\left( {\matrix{ n \cr k \cr } } \right)(k - 1)!(n - k)!$$

Why?

$\endgroup$
4
$\begingroup$

You have given the correct answer to the following question: how many permutations are there in which $k$ is smaller than all the numbers to its right and larger than all the numbers to its left. However the last part was not specified in the question you asked. For example if $n=7$ and $k=3$ then $$(2,7,1,4,3,5,6)$$ is an allowable permutation, but you will not have counted it.

Hint. First determine which places $k$ can occupy. If $j$ is such a place then

  • there are $n-k$ numbers larger than $k$, and you have to choose $n-j$ of them, in a particular order, to occupy the places to the right of $k$;
  • There are now $j-1$ numbers which have to be placed in a particular order to the left of $k$.

So the answer will be $$\sum_{j=?}^{?} (?)(?)$$ - see if you can fill in what is missing.

On second thoughts here is another argument which leads directly to the answer you were given.

  • Choose (without regard to order) the places to be occupied by the numbers $1,\ldots,k$.
  • Choose the order for these numbers, remembering that $k$ must be last.
  • Order the remaining $n-k$ numbers into the remaining $n-k$ places.

Best of all: the answer you were given simplifies to $$\frac{n!}{k}\ .$$ Here is an argument which gives this result immediately. There are $n!$ permutations of the numbers altogether, and we determine the proportion of them which satisfy your conditions. As in my second solution, the only thing that matters is that $k$ should be the last of the numbers $1,\ldots,k$ to appear in the permutation: as long as this is true, the locations of the larger numbers don't matter. Among all orderings of the numbers $1,\ldots,k$, the number $k$ occurs with equal frequency in each of the $k$ places; so the proportion in which it occurs last is $1/k$, and the number of permutations of $1,\ldots,n$ in which this occurs is $$\frac{n!}{k}$$ as claimed.

$\endgroup$
3
$\begingroup$

Hint: We do not have to place $k$ in the $k$-th cell. We can place it in any of the cells that are in the $k$-th position or later.

$\endgroup$
1
$\begingroup$

take the original combination with k at kth position ..call it initial position number of ways = (k−1)!(n−k)! now remove one from right of of k in initial position and put to left of k and arrange them number of ways = (k)!(n−k-1)! (n-k,1) now remove 2 from right of k in initial position and put to the left of k and arrange them number of ways = (k+1)!(n−k-2)! (n-k,2) . . . . overall number of ways = ∑(from r=0 to r= n-k) {(n-k,r)(n-k-r)!(k+r-1)!} rearrange it and get overall number of ways = (k-1)!(n-k)!∑(same limits) { (k-1+r,r)}

$\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.