# Permutations with restrcitions

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 ?

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

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)$.

• 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 ? – Policy violater Jan 4 '16 at 9:36