quick reply needed- circular permutation

For discussing Olympiad Level Combinatorics problems
User avatar
Avik Roy
Posts:156
Joined:Tue Dec 07, 2010 2:07 am
quick reply needed- circular permutation

Unread post by Avik Roy » Thu Jan 27, 2011 5:31 pm

I'm not being able to crack the following :S
$5$ couples are to be arranged in a circular table so that nobody sits beside his/her partner. In how many ways is this possible?
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

abir91
Posts:52
Joined:Sun Dec 19, 2010 11:48 am

Re: quick reply needed- circular permutation

Unread post by abir91 » Thu Jan 27, 2011 8:15 pm

You might want to check out Lucas problem of marriage couples. Removing some condition from that problem gives us this problem. So here is my solution (apologies in advance if it is wrong again!):
Let, $A_i $ = Set of all permutations with at least the $i^{th}$ couple sitting together. To find the union, we use inclusion-exclusion principle. So, first choose $i$ couples first, then place them, then place the other people one by one. That is, if there are $k$ people sitting then $(k+1)^{th}$ person can sit in $k$ seats and so on. After some simplification the formula looks like this:

\[ S = (2n-1)! + \sum_{i=1}^{n} (-1)^{i} \binom{n}{i} 2^i \; (2n-i-1)! \]
Note: The previous solution was wrong. I have checked this one with small values of $n$ and gives correct answer. Anyone got any other solution? :)
Last edited by abir91 on Fri Jan 28, 2011 12:53 pm, edited 1 time in total.
Reason: Fixed a bug in the previous solution
Abir

Have you read the Forum Rules and Guidelines?

photon
Posts:186
Joined:Sat Feb 05, 2011 3:39 pm
Location:dhaka
Contact:

Re: quick reply needed- circular permutation

Unread post by photon » Sun Feb 06, 2011 9:40 pm

Sorry,i haven't read lucas' theorem.So what about my solution (a little bit confused)? :?
Suppose there is no condition for sitting.So we can make 10! ways for sitting.
Now suppose the couples have to sit by partners.That's time permutation is 32*5! (each couple makes 2!ways)
Therefore,10!-32*5! ways....
Please,post.If it is correct or not....
Try not to become a man of success but rather to become a man of value.-Albert Einstein

abir91
Posts:52
Joined:Sun Dec 19, 2010 11:48 am

Re: quick reply needed- circular permutation

Unread post by abir91 » Sun Feb 06, 2011 9:46 pm

It is not correct as you have to deduct cases where there are less than five couples sitting together.

Note that, I did not mention anything about Lucas Theorem. It is about "Lucas's Problem of Marriage Couple", which is quite different from his many theorems.

Good try though. You are close, keep trying :)
Abir

Have you read the Forum Rules and Guidelines?

photon
Posts:186
Joined:Sat Feb 05, 2011 3:39 pm
Location:dhaka
Contact:

Re: quick reply needed- circular permutation

Unread post by photon » Sun Feb 06, 2011 10:12 pm

hey i guess i got it !!! :)
that doesn't matter only of 5 couples together permutation.we can get 4 couples together and one may be together or not and so on.....
we get 32*5!+16*6!+8*7!+4*8!+2*9! ways where 1 or more than 1 couple can get by partner.
so ans. is 10!-(32*5!+16*6!+8*7!+4*8!+2*9!)ways...
Try not to become a man of success but rather to become a man of value.-Albert Einstein

Abhijit Mondal
Posts:1
Joined:Wed Jan 26, 2011 8:31 pm

Re: quick reply needed- circular permutation

Unread post by Abhijit Mondal » Mon Feb 07, 2011 10:37 pm

i think it is 10!-(10*7)(8*5)(6*3)(4*1)(1*1)

photon
Posts:186
Joined:Sat Feb 05, 2011 3:39 pm
Location:dhaka
Contact:

Re: quick reply needed- circular permutation

Unread post by photon » Tue Feb 08, 2011 2:06 pm

Please explain :P
Try not to become a man of success but rather to become a man of value.-Albert Einstein

Post Reply