# List of non-immediately-repeating permutations

Background: I am trying to design a scientific trial (computer science dissertation) in which participants will answer 8 questions. There are in fact only 4 questions but each is asked in two different ways, so there are 4 unique correct answers, let's call them a, b, c and d. So the set of correct answers will be {a, a, b, b, c, c, d, d}.

The 8 trial questions must appear in a random order however no question with the same correct answer must appear immediately after the other. So e.g. asking a question with answer a means the next question must not also have answer a.

I would like to produce a list of the permutations of {a, a, b, b, c, c, d, d} that do not repeat in this way. I am trying to write an algorithm for this but I'm having a little trouble with the mathematics. Any help would be greatly appreciated.

Could anyone give me some hints on how to either produce this list or how to reduce the list of 2520 permutations of {a, a, b, b, c, c, d, d} to only contain permutations with my condition?

Thanks.

• P.s. if anyone can suggest software or e.g. a method to do this in Mathematica that would be fine too! Jan 12, 2012 at 0:51
• UPDATE: I believe I found a tool that does it at users.telenet.be/vdmoortel/dirk/Maths/permutations.html however I do not trust the output. It produces 864 permutations. Can anyone help me prove this is the number of permutations I was looking for? Jan 12, 2012 at 1:03
• Wonderful! Thanks for that find! Jan 12, 2012 at 1:29

I know your question as a married couple seating problem: $n$ couples go to the cinema and for some reason spouses do not want to sit next to each other.

The number can be calculated by inclusion-exclusion: you calculate the total number of ways the eight answers can be arranged $8!/2^4$, subtract the number where one pair is stuck together $4\times 7!/2^3$, add the number where two pairs are stuck together ${4 \choose 2}\times 6!/2^2$, subtract ${4 \choose 3}\times 5!/2^1$ and add ${4 \choose 4}\times 4!/2^0$. This gives a result of 864.

So in general you have $$\sum_{i=0}^n (-1)^i {n \choose i} (2n-i)! / 2^{n-i}$$ and in fact the $n=0$ and $n=1$ terms cancel out.

Although there may only be 2520 permutations of your four pairs of answers, there are in fact 40320 permutations of the questions in total ($2^4$ times as many). Similarly there are $2^4$ times as many acceptable permutations of the questions where no identical answers are together, i.e. 13824 and the general term becomes $$\sum_{i=0 }^n (-2)^i {n \choose i} (2n-i)!$$

OEIS A114938 and A007060 give more terms if you need them. It looks as if for a large number of pairs, about 36.7% of permutations meet the required condition, so an easy way to generate one in particular rather than all at once might be to take a random permutation but if it fails choose another until you have one which meets the condition.

• I just wanted to thank you for your very clear description. You have helped me tremendously to understand the theory enough to feel confident that my trial design is correct. Jan 22, 2012 at 15:23
• Harry. may I ask how you calculated that about 36.7% of permutations meet my required condition of non-consecutive permutations? Apr 20, 2012 at 2:50
• Henry, not Harry. I took the second expression for large $n$ and divided it by $(2n)!$ [I could have taken the first and divided it by $(2n)!/2^n$] and then looked at what value it tended towards. For example, using the R code sum((-2)^(0:n) * choose(n,0:n) * factorial(2*n - (0:n)) ) / factorial(2*n) for $n=4$ I get 0.3428571 but for $n=64$ I get 0.366434 Apr 22, 2012 at 9:59
• By the way - 36.7% is approximately $\frac{1}{e}$, and I'm sure there's a reason why! Jan 17, 2015 at 17:14
• @Vincent Tjeng: see math.stackexchange.com/questions/465318/… for yet another question which converges to $\exp(-1)$. It is a common limit for such questions Jan 17, 2015 at 19:53

In case you do still need code in Mathematica to solve your problem - this should give you exactly what you need.

Characters /@ (Select[#, StringFreeQ[#, RegularExpression["aa|bb|cc|dd"]] &] &@ Map[StringJoin, #, 1] &@Permutations[Characters["aabbccdd"]])

• do comment if you'd like me to explain the code! Mar 24, 2013 at 9:43