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

The Gateway to Computer Science Excellence

+3 votes

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

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

0 votes

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

0

by taking sample example, i conclude B is correct.

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

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

52,314 questions

60,435 answers

201,773 comments

95,251 users