# number of possible permutations in arranging elements

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

• I have updated the way in which i have tried @JoséCarlosSantos – jarvis Jun 17 '18 at 17:58
• I have edited your question (with some changes to the test). Please confirm that this is your intended question. – Michael Burr Jun 18 '18 at 11:13
• 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$. – joriki Jun 18 '18 at 12:00