4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Ross Millikan Jan 16 '14 at 16:36
  • $\begingroup$ For four couples I get $1296$ by hand count. $\endgroup$ – Ross Millikan Jan 16 '14 at 17:01
  • $\begingroup$ 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 $\endgroup$ – KBusc Jan 16 '14 at 17:02
  • $\begingroup$ @RossMillikan how did oyu get that? $\endgroup$ – KBusc Jan 16 '14 at 17:02
  • $\begingroup$ @KBusc Your small numbers indicate that you want to regard rotated seatings as equivalent, but you should say so explicitly. $\endgroup$ – Phira Jan 17 '14 at 9:50
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – KBusc Jan 17 '14 at 12:10
  • $\begingroup$ 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/… $\endgroup$ – KBusc Jan 17 '14 at 12:12
  • $\begingroup$ @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.) $\endgroup$ – user84413 Jan 17 '14 at 16:23
  • $\begingroup$ Thank you for all of your help It's truly appreciated $\endgroup$ – KBusc Jan 17 '14 at 16:45
  • $\begingroup$ 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. $\endgroup$ – KBusc Jan 17 '14 at 17:23
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thank you I understand the method for this but I don's see yet how to generalize it. Any suggestions? $\endgroup$ – KBusc Jan 16 '14 at 17:17
  • $\begingroup$ 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) $\endgroup$ – Ross Millikan Jan 16 '14 at 17:21
  • $\begingroup$ I think I can write the program to do it so I will give it a shot. Thank you for your help $\endgroup$ – KBusc Jan 16 '14 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.