88 views

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?$

1. $\binom{n}{k}-\binom{n}{(k+1)}$
2. $\frac{n!}{k!}-\frac{n!}{(k+1)!}$
3. $\frac{n!}{(k+1)!}-\frac{n!}{(k+2)!}$
4. $\binom{n}{(k+1)}-\binom{n}{(k+2)}$

recategorized | 88 views

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



by
edited by
0
by taking sample example, i conclude B is correct.

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

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