CMI2019-A-5

Question

Let $\pi=[x_{1},x_{2},\cdots,x_{n}]$ be a permutation of $\{1,2,\cdots,n\}.$ For $k<n,$ we say that $\pi$ has its first ascent at $k$ if $x_{1}>x_{2}\cdots>x_{k}$ and $x_{k}<x_{k+1}.$ How many permutations have their first ascent at $k?$

• A. $\binom{n}{k}-\binom{n}{(k+1)}$
• B. $\frac{n!}{k!}-\frac{n!}{(k+1)!}$
• C. $\frac{n!}{(k+1)!}-\frac{n!}{(k+2)!}$
• D. $\binom{n}{(k+1)}-\binom{n}{(k+2)}$

Answer 1

This is an excellent question!

After observing the patterns, we can clearly see that if we’re talking about k, then we need a  total of k + 1 numbers, such that first k-1 are arranged in descending order, the kth number should be minimum, and the number at k+1th position will always be greater than the kth position number(as the kth position number is minimum).

Now, the first task is to select k+1 numbers out of n,

and the second task is to place a number except the minimum of these k+1 numbers at the (k+1)th position,

and the third task is to permute the remaining n-(k+1) numbers which were untouched from the beginning. The n-(k+1) numbers will permute in (n-(k+1))! ways.

So, task1 = nC(k+1)

task 2 = k ways(except minimum, we have k choices)

task3 = (n-(k+1))!

So, total permutations = nC(k+1) * k * (n – (k + 1))!

On computing the answer will come out to be option B.

Answer 2

$\underline {\bf{Answer}}:\bf B$

 

$\underline{\bf{Explanation:}}$

An ascent at any position $\bf{i < n}$ is given for the value which follows $\bf{i}$ is larger than the current value.

$\underline{\bf{Example:}}$

Number of ascents for $(1, 2, 3, 4)$ are $:-$

$ ({1, 2}), ({2, 3}), ({3, 4})$

Now, coming to the question, a permutation is obtained by taking $\bf{i}$ elements for the first $\bf{i}$ positions (which are sorted in descending order) & then taking a permutation of the remaining $(\bf{n-i})$ elements.

$\therefore \mathrm {|P_i| =  \binom{n}{i}\ .(n-i)! = \frac{n!}{i}}$

$\therefore$ Answer$\mathrm{ = |P_k|- |P_{k+1}| = \frac{n!}{k!} -\frac {n!}{(k+1)!}}$

$\therefore \bf B$ is the correct option.

---

Further Reading: https://en.wikipedia.org/wiki/Permutation#Ascents,_descents,_runs_and_excedances

 

Comments

by taking sample example, i conclude B is correct.

But i am not getting your answer, why you subtracted P$_{K+1}$ ?

---

See the order is given till $x_1 > x_2 >... x_k$ and after that $ x_k  < x_{k+1}$

For example:

6 5 4 3 2 10

Say, $k = 5$, above

here $x_5 < x_{5+1}$

So, how will you calculate ascent?

Simply calculating the permutations till you are sure about the order and then subtracting the k+1 permutations.

 

For beautiful explanations of ascent, descent and eulerian number. formula:

https://en.wikipedia.org/wiki/Permutation#Ascents,_descents,_runs_and_excedances

Answer 3