0
$\begingroup$

Hi I've got a permutation problem and I wonder if there is some neat solution to it instead of my brute force method?

I've tried to simplify my problem to make it as easy as possible to interpret and understand.


Problem

Suppose we have 4 boys which I call $X$ and 4 girls which I call $Y$. The boys and the girls are in a classroom that has 6 tables, each table has 2 chairs, so there is a total of 12 chairs.

The rules are the following: 2 of the boys must share a table with 2 of the girls. NO boy is allowed to share a table with another boy and NO girl is allowed to share a table with another girl.

How many ways can we assign the boys and the girls to the chairs so that the rules stated above are fulfilled? I will denote a table with two chairs as "(..)"

I.e. we begin with the setup

$(..)(..)(..)(..)(..)(..)$

Suppose we decide to seat one of the girls first. There are 12 different chairs we could assign the first girl to

$12(..)(..)(..)(..)(..)(.Y)$

The second girl can be assigned to 10 different chairs since we don't allow any (YY) combinations. So

$12\cdot10(..)(..) (..) (..) (.Y) (.Y)$

After we have seated all the girls we have

$12\cdot10\cdot8\cdot6(..)(..) (.Y) (.Y) (.Y) (.Y)$

Now when we are going to assign the first boy to one of the empty chairs. We can either assign him to a table that's empty or we can let him share a table with a girl.

$12\cdot10\cdot8\cdot6\cdot4[(..)(.X) (.Y) (.Y) (.Y) (.Y)+(..)(..) (XY) (.Y) (.Y) (.Y)]$

Assigning the second boy to a chair we have the following combinations

$12\cdot10\cdot8\cdot6\cdot4 [2(.X)(.X) (.Y) (.Y) (.Y) (.Y) +8(..)(.X) (XY) (.Y) (.Y) (.Y) +3(..)(..) (XY) (XY) (.Y) (.Y)]$

Now remember that we do not allow more than two $(XY)$ combinations! Thus for the third boy we get

$12\cdot10\cdot8\cdot6\cdot4 [24(.X)(.X) (XY) (.Y) (.Y) (.Y) +36(..)(.X) (XY) (XY) (.Y) (.Y)]$

And finally for the last boy we get

$12\cdot10\cdot8\cdot6\cdot4 [72(.X)(.X) (XY) (XY) (.Y) (.Y) +72(.X)(.X) (XY) (XY) (.Y) (.Y)]$

Which can be simplified to

$72\cdot12\cdot10\cdot8\cdot6\cdot4\cdot2 (.X)(.X) (XY) (XY) (.Y) (.Y)$

So $72\cdot12\cdot10\cdot8\cdot6\cdot4\cdot2$ give us a total of $3317760$ number of ways to assign the boys and the girls to the chairs!


My question: My solution is not that pretty, it just pure brute force. Is there a better and more elegant way to encode the solution to the problem instead of my brute force method?

EDIT1: The children and the tables and the chairs are distinguishable.

EDIT2: You are allowed to change the order of the chairs within a table so that for example $(YX)=(XY)$

$\endgroup$
7
  • $\begingroup$ Are the tables distinguishable? Are the chairs at a table distinguishable? Are the boys distinguishable? Are the girls distinguishable? $\endgroup$
    – Bram28
    Jan 28, 2018 at 17:33
  • $\begingroup$ Are the children distinguishable? $\endgroup$
    – user76568
    Jan 28, 2018 at 17:38
  • $\begingroup$ @Bram28 The boys/girls, chairs and tables are all indistinguishable. $\endgroup$ Jan 28, 2018 at 17:43
  • $\begingroup$ @Dror The boys are indistinguishable from the boys and the girls are indistinguishable from the girls. $\endgroup$ Jan 28, 2018 at 17:44
  • $\begingroup$ @Turbotanten Well, then your calculations seem to immediately have a problem, since right at the start you say that the first girl can be seated in one of 12 chairs ... but if all tables are chairs are indistinguishable, then sitting the first person in whichever chair is all the same. Indeed, if ther tables and chairs are all indistinguishable, then as far as sitting the girls go, there is only $1$ possibility: have them sit at different tables! $\endgroup$
    – Bram28
    Jan 28, 2018 at 17:54

1 Answer 1

2
$\begingroup$

If the tables, chairs, boys, and girls are all indistinguishable, and if the rule:

2 of the boys must share a table with 2 of the girls.

is interpreted (as you do) as there being exactly $2$ tables with a boy and a girl (as opposed to there being at least $2$ tables with a boy and a girl), then there is exactly $1$ possibility here: have $2$ tables with a boy and a girl, $2$ tables with a boy, and $2$ tables with a girl.

Are you sure that there cannot be more than $2$ tables with a boy and a girl?

EDIT

If the tables are distinguishable, and the chairs are, but the boys are not, and girls are not, you are still overcounting: For example, sitting the first girl at table $1$, chair $a$, and the second girl at table $2$, chair $a$, is the same thing as putting the first girl at table $2$, chair $a$, and the second at table $1$, chair $a$.... exactly because the girls are indistinguishable.

Similarly, you are overcounting the number of ways we can sit down the boys because you make a difference between putting the first boy at a table with a girl, and the second one not, and vice versa, but if the boys are indistinguishable, those two actions amount to the same thing.

So, for the girls you just need to pick the $4$ tables out of $6$ where the girls are going to sit, and multiply by $2^4$ since the chairs are distinguishable. So that's ${6 \choose 4} = 15$ times $16$ is $240$ possibilities.

For the boys: first you need to create two tables with a boy and a girl ... i.e. pick $2$ out of the $4$ tables with a girl: that's ${4 \choose 2} = 6$ possibilities. Then, for the last two boys the last two tables are determined, but they do have a choice of $2$ chairs each, so that's another factor of $4$

So, you have a total of $240 \cdot 6 \cdot 4= 5760$ possibilities.

$\endgroup$
8
  • $\begingroup$ Can't the children refuse to sit? $\endgroup$
    – user76568
    Jan 28, 2018 at 18:03
  • $\begingroup$ @Dror Heehee, thinking outside the box :) $\endgroup$
    – Bram28
    Jan 28, 2018 at 18:04
  • $\begingroup$ @Dror No the children can't refuse to sit xD $\endgroup$ Jan 28, 2018 at 18:05
  • $\begingroup$ @Bram28 There cannot be more nor less than 2 tables with a boy and a girl $\endgroup$ Jan 28, 2018 at 18:05
  • 1
    $\begingroup$ @turbotanten ok, then muliply my answer by $4!$ to distinguish the girls, and another $4!$ for the boys... does that equal your answer? $\endgroup$
    – Bram28
    Jan 28, 2018 at 18:58

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.