The Gateway to Computer Science Excellence
+1 vote
35 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)}$
in Others by Boss (16.8k points)
recategorized by | 35 views

1 Answer

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

 

 

by Boss (13.2k points)
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,696 users