1
$\begingroup$

I have n distinct numbers , so I will have n! permutations. Now I want to insert another number into this set , and find the total number of new permutations. But there are some restrictions. This new number cannot be placed adjacent to k numbers in the list of n. So how many such permutations are possible.

eg.

I have 1 , 2 , 3 , 4. So there are 24 permutations of this set. Now I want to add 5 to the list, so that it doesnt come adjacent 2 and 3. So how do I find it? (So n = 4 and k = 2 in this case)

Is there any generalization like for n, k ?

$\endgroup$
  • $\begingroup$ How does one get from $k$ to the numbers $2$ and $3$ to be no neighbours? $\endgroup$ – mvw Jan 3 '16 at 20:28
  • $\begingroup$ k = 2 as there are total of two numbers which cannot be neighbours to 5. $\endgroup$ – Policy violater Jan 4 '16 at 6:02
  • $\begingroup$ @mvw , I guess this is what you asked ! $\endgroup$ – Policy violater Jan 4 '16 at 9:43
  • 1
    $\begingroup$ This question appears to be from an open competition. $\endgroup$ – Frentos Jan 4 '16 at 11:21
  • $\begingroup$ Locking and temporarily deleting the answers because this is an ongoing contest. Shame on the asker for asking it thrice! $\endgroup$ – Jyrki Lahtonen Jan 4 '16 at 12:55
2
$\begingroup$

Let's use symbol $X$ to indicate the new number, and $O$ to indicate the $n-k$ numbers which are allowed to be adjacent to $X$. There are 3 case:

$\cdots OXO \cdots$, in this case you can put the two good elements in $(n-k)(n-k-1)$ ways. Now consider the entire block like a single element and shuffle the remaining $n-2$ elements with it, in $(n-1)!$ ways. We get $(n-k)(n-k-1)(n-1)!$.

The second case is

$XO \cdots$, put the adjacent element in $n-k$ ways, then you can put the rest of the element on the right of this block in $(n-1)!$ ways. We get $(n-k)(n-1)!$.

The third case is

$\cdots OX$, put the adjacent element in $n-k$ ways, then you can put the rest of the element on the left of this block in $(n-1)!$ ways. We get $(n-k)(n-1)!$ again.

Sum it up:

$(n-k)(n-k-1)(n-1)! + 2(n-k)(n-1)! = (n-k)(n-1)!(n-k+1)$.

$\endgroup$
  • $\begingroup$ Okay , Thanks for the explanation. But can you answer another question , what if, the previous n numbers were themselves in some form restricted permutation , and instead of n! permutation there were lets say f(n) permutations , how would the approach change then ? $\endgroup$ – Policy violater Jan 4 '16 at 9:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.