permutation of 2n numbers with a window of n

320 Views Asked by At

I am stuck in a question for a while,
Consider 2 list of alphabets,

1 2 3 4  
a b c d  
y x w v 

the questions asks to count the number of ordering/permutations possible,there are also some rules to be followed,
no matter the ordering all positions must add up to z, i.e a+y = z, b+x=z

  1 2 3 4         1 2 3 4  
  a x w d         a x b d  
  y b c v         y c w v
  accepted         not accepted

Now I managed to find out that if all the elements are unique, it follows the double factorial of evens
for this example ,n=4 ans is $384$
I just cant find how to handle duplicates, for example

  1 2 3  
  m m a  
  m m y

The answer is 6, if all elements were unique it would been 48 , I just cant figure, how to calculate this given the lists
example, keeping a,y constant. So basically there will be 6*8=48 oderings

  a b c   a c b   a w x   a x w  a b w
  y x w   y w x   y c b   y b c  y x c  

  a c x   a c w   a x c
  y w b   y w b   y b w 

if there are duplicates,

  m a   m y   a m  y m
  m y   m a   y m  a m  

as you can see, if there are duplicates they dont follow the $2^n(n!)$, due to non distinct permutations

1

There are 1 best solutions below

10
On BEST ANSWER

OK, I hope I’ve now, on the third try, understood the question. Next time, it would be preferable if you’d state the problem in clear general terms rather than merely providing examples and letting us generalize from them.

From what I gather from the examples, it seems that what you’re actually interested in is the number of arrangements of a given multiset of letters in two rows, where each letter can go anywhere in either row, under the condition that the letters in the same column must add up z. You seem to be assuming that the given multiset consists of pairs that add up to z, so that such an arrangement is in fact possible.

If the multiset contains m $2m$ times and $n_k$ copies of each other type of pair for $1\le k\le12$, for a total of $s=m+\sum_kn_k$ columns, then the number of admissible arrangements is

$$ \frac{s!}{m!\prod_kn_k!}2^{s-m}\;. $$

There are $s!$ permutations of the pairs, but for each type of pair we need to divide by the number of permutations among that type, since the result is invariant under them. And we have to multiply by a factor $2$ for each pair that’s not mm, since for each such pair there’s an independent binary choice which of the two letters to put in the top row.