Results 1 to 5 of 5

Math Help - round table 2

  1. #1
    Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    181
    Thanks
    1

    round table 2

    4 married couples sit at a round table. How many ways can they sit if each couple must sit seperately?

    There is a formula for this solution but I couldn't get it.


    Always, always, start a new thread for a new question.

    Using inclusion/exclusion
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    181
    Thanks
    1

    Re: round table 2

    4 married couples sit at a round table. How many ways can they sit if each couple must sit seperately?

    There is a formula for this solution but I couldn't get it. I am sorry I wanted to make some edits to my former post but I couldn't I just wanted to past the formula but I also pasted some messages with it I am sorry
    Last edited by kastamonu; February 20th 2013 at 07:25 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    south africa
    Posts
    11

    Re: round table 2

    I don't have a clue about the equation to solve this but I managed to do it brute force with Python.

    Code:
    >>> import itertools
    >>> couples = {0:1, 2:3, 4:5, 6:7}
    >>> for k,v in couples.items():
    	couples[v] = k
    
    	
    >>> all_positions = list(itertools.permutations(range(8)))
    >>> def is_valid(position):
    	if position[0] == couples[position[-1]]:
    		return False
    	for p in range(len(position) - 1):
    		if position[p] == couples[position[p+1]]:
    			return False
    	return True
    
    >>> all_positions = [p for p in all_positions if is_valid(p)]
    >>> len(all_positions)
    11904
    >>>
    seems to be 11904
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: round table 2

    Quote Originally Posted by russ123 View Post
    I don't have a clue about the equation to solve this but I managed to do it brute force with Python.
    Code:
    >>> import itertools
    >>> couples = {0:1, 2:3, 4:5, 6:7}
    >>> for k,v in couples.items():
    	couples[v] = k
    >>> all_positions = list(itertools.permutations(range(8)))
    >>> def is_valid(position):
    	if position[0] == couples[position[-1]]:
    		return False
    	for p in range(len(position) - 1):
    		if position[p] == couples[position[p+1]]:
    			return False
    	return True
    >>> all_positions = [p for p in all_positions if is_valid(p)]
    >>> len(all_positions)
    11904>>>
    seems to be 11904

    That is a gross over-count. There are only 7!=5040 ways to seat eight people at a around table.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2012
    From
    south africa
    Posts
    11

    Re: round table 2

    Sorry, I didn't know the exact positions of the seats didn't matter, that only the relative positions mattered then I can see how it's 7!

    --- edit ---

    I tried to correct my mistake and got a much lower figure: 1488
    ...but I wonder if it's right this time. If so then this will tell you the answer for any number of couples

    Code:
    from itertools import permutations
    
    def check(config):
        '''
        return True if no couples are next to each other
        False otherwise
        '''
        if config[0] == 0 or config[-1] == 0:
            return False
        else:
            for x in range(len(config) - 1):
                if config[x] == config[x + 1]:
                    return False
        return True
    
    
    while True:
        couples = int(raw_input("couples: "))
        all_configs = [0] + (range(1, couples) * 2)
        all_configs = [c for c in list(permutations(all_configs)) if check(c)]
        print len(all_configs)
    Last edited by russ123; February 25th 2013 at 01:09 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. round table
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 18th 2013, 12:00 PM
  2. Round Table
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: January 26th 2013, 10:52 AM
  3. Round Table Problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 12th 2012, 04:12 PM
  4. The round Table
    Posted in the Geometry Forum
    Replies: 1
    Last Post: September 11th 2010, 10:06 AM
  5. Round Up
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 25th 2008, 04:44 PM

Search Tags


/mathhelpforum @mathhelpforum