In how many ways can you arrange a circle of partners so that no partners are touching?

There are a lot of similar questions to this but none that is quite the same so I figured I would ask a new question. The problem is you have a group of people that came in pairs, in how many ways can the $N$ people be arranged in a circle such that no person in the circle is holding hands with the partner they came with.

I have worked out by hand that for two couples(four people) the answer is $2$ ways

For three couples ($6$ people) the answer is $32$ ways

Also it should be noted that a rotated circle is not counted as a different arrangement.

If the answer posted below is correct the OEIS sequence is http://oeis.org/A129348 Can any one else confirm that this is correct?

• This is similar to math.stackexchange.com/questions/391734/…, but that one has a linear order, not circular. I didn't find anything helpful in OEIS – Ross Millikan Jan 16 '14 at 16:36
• For four couples I get $1296$ by hand count. – Ross Millikan Jan 16 '14 at 17:01
• Yes Ive checked the OEIS using both 2,32 and 0,2,32 but no luck. And I have read the linear ones a few times over but I cannot wrap my head around how to reapply those methods to this circular problem – KBusc Jan 16 '14 at 17:02
• @RossMillikan how did oyu get that? – KBusc Jan 16 '14 at 17:02
• @KBusc Your small numbers indicate that you want to regard rotated seatings as equivalent, but you should say so explicitly. – Phira Jan 17 '14 at 9:50

Let m be the number of pairs, so that $n=2m$.

Let S be the set of all seatings of the pairs in a circle, and

let $E_i$ be the set of seatings in which pair i is together, for $1\le i\le m$.

Using Inclusion-Exclusion and the fact that n people can be seated in a circle in $(n-1)!$ ways,

$\displaystyle|\overline{E_1}\cap\cdots\cap\overline{E_m}|=|S|-\sum_{i}|E_i|+\sum_{i<j}|E_i\cap E_j|-\sum_{i<j<k}|E_i\cap E_j\cap E_k|+\cdots+(-1)^m|E_1\cap\cdots\cap E_m|$

$\;=(2m-1)!-\binom{m}{1}2^1(2m-2)!+\binom{m}{2}2^2(2m-3)!-\binom{m}{3}2^3(2m-4)!+\cdots+(-1)^m\binom{m}{m}2^m(m-1)!$

$\;\;=\displaystyle\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}2^{i}(2m-i-1)!$.

• I can see that there is a summation that can be written here. But I am unsure how to format it. Could you please rewrite the above as a summation from 0 to m – KBusc Jan 17 '14 at 12:10
• I also dont know if that is correct because how is that different from if they were sitting in a straight line? math.stackexchange.com/questions/391734/… – KBusc Jan 17 '14 at 12:12
• @KBusc I inserted a missing sign in the last term, and wrote the answer in summation notation. The answer is similar to the case in which people are sitting in a line, but the factorials are different. (If you check, this formula should give the right answer for m=3 and m=4; see leonbloy's answer below.) – user84413 Jan 17 '14 at 16:23
• Thank you for all of your help It's truly appreciated – KBusc Jan 17 '14 at 16:45
• I would like to add this sequence to the OEIS. But I would not like to take credit for work I did not do. I would like to add the above formula and I would like to add your name as well. If this is ok with you please email me, my email is in my profile. – KBusc Jan 17 '14 at 17:23

Here is the calculation for $8:$

Seat one person of the first couple. This fixes the rotation of the circle. Seat the second person of the first couple. The remaining seats can be in groups of $1+5 (2$ ways), $2+4 (2$ ways), or $3+3, (1$ way).

From $1+5$ we can go to $4$ in $4$ ways, $1+3$ in $6$ ways, $2+2$ in $2$ ways, $1+1+2$ in $4$ ways, or $1+1+1+1$ in $2$ ways.
Similarly we can go from $2+4$ to $1+3$ in $8$ ways or to $1+1+2$ in $12$ ways.
We can go from $3+3$ to $1+3$ in $4$ ways, $2+2$ in $8$ ways, $1+1+2$ in $8$ ways, or $1+1+1+1$ in $2$ ways.

Multiplying out, after two couples we can have $4$ in $8$ ways, $1+3$ in $32$ ways, $2+2$ in $12$ ways, $1+1+2$ in $40$ ways or $1+1+1+1$ in $6$ ways.

Finally, from $4$ we can place the last two couples in $8$ ways, $1+3$ in $8$ ways, $2+2$ in $16$ ways, $1+1+2$ in $16$ ways, and $1+1+1+1$ in $24$ ways.

The total comes out $1296$

• Thank you I understand the method for this but I don's see yet how to generalize it. Any suggestions? – KBusc Jan 16 '14 at 17:17
• I don't see a way to generalize either. My organization saves recalculating the ways to fill (for example) 1+3 between coming from 1+5, 2+4, or 3+3, which makes 8 accessible by hand. I think for $10$ or up you would need a computer program. A nice bactracking program could go a ways, but would be a challenge to write (at least for me) – Ross Millikan Jan 16 '14 at 17:21
• I think I can write the program to do it so I will give it a shot. Thank you for your help – KBusc Jan 16 '14 at 17:52