2

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 ?

user253651
  • 237

1 Answers1

3

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

Maffred
  • 4,016
  • 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 ? – user253651 Jan 04 '16 at 09:36