I have a sequence of length $N$ created by removing some elements (possibly zero) from a permutation of numbers $(1,2,\dots,N)$. When an element is removed, the length of the sequence doesn't change, but there is an empty spot left where the removed element was, denoted by $\ast$. You also have an integer $K$.

Let's call a permutation $p_1,p_2,\dots,p_N$ good if:

it is possible replace empty spots in the permutation by numbers in such a way that we obtain the permutation $p$ where the number of positions $i$ ( $1 < i \leq N$ ) such that $p_i > p_{i−1}$ is equal to $K$ My task is to find the number of good permutations.

Eg. When $n=3$ elements and $K=1$: Given the array $(2 ,* ,*)$, then the answer$=2$ explanation: two possible ways $(2,3,1)$ and $(2,1,3)$

I have tried as $f=$number of * in array, ans as $(f)!-k$

but this gives me wrong answer.

pls help me derive the formula

  • $\begingroup$ I have updated the way in which i have tried @JoséCarlosSantos $\endgroup$ – jarvis Jun 17 '18 at 17:58
  • $\begingroup$ I have edited your question (with some changes to the test). Please confirm that this is your intended question. $\endgroup$ – Michael Burr Jun 18 '18 at 11:13
  • $\begingroup$ Where you have "we obtain the permutation $p$" it appears that you mean "we obtain a permutation $p$"? Because no permutation $p$ had previously been introduced, and you go on to provide conditions characterizing $p$. $\endgroup$ – joriki Jun 18 '18 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.