0

What is the difference between the number of combinations you can make when forming a line with 8 girls and 6 boys where at most 3 of the same gender can only be adjacent to each other to when you arrange them in a round circle with the same rule?

In the first scenario we have 6 boys and 8 girls. And only at most 3 of the same gender can be adjacent. So I can treat this as a random 14 letter arrangement like: ${A,B,C,D,E,F,G,H,a,b,c,d,e,f}$

Where only at most 3 uppercase letters and 3 lowercase letters can be adjacent to each other. So the total number of arrangments is $14!$ ways without restrictions.

The second scenario has the same number of students and restrictions. But the total number of arrangments is $(14-1)!$

So my question is, how can I form an expression for both of the scenarios so that I can find their total number of arrangements with the restrictions since I am looking for their difference?

Willie Taylor
  • 69
  • Are you certain that you are supposed to treat the children as individuals? The problem might only be concerned with the patterns of boys and girls. That's how I read it, but I can't make a case for one interpretation or the other. In other words, I think of it as how many ways can we arrange $8$ B's and $6$ G's so that the same letter doesn't appear $3$ times consecutively. In any case, once you get the answer, it's easy to transform one to the other, by multiplying (or dividing) by $8!6!$. – saulspatz Apr 21 '20 at 19:08
  • You are specifically asked just for the difference between the numbers, not the numbers themselves. Is that correct? – saulspatz Apr 21 '20 at 19:39
  • Yes I am just asking for the difference of number of arrangments between the 2 of them. I just need to find how many possible arrangments with the given restriction does each one have – Willie Taylor Apr 21 '20 at 19:49
  • I wa hoping there was some clever way to figure out the difference without having to figure out both numbers, but I haven't been able to find it. – saulspatz Apr 21 '20 at 20:04
  • Do you know how to figure out both numbers? – Willie Taylor Apr 21 '20 at 20:06
  • Only by brute force. I know by a computer script that there are $300$ ways to arrange them in a row, without regard to their identities, so $300\cdot8!\cdot6!$ in all. Of the $300$ ways there are $196=14^2$ that we could close into a circle without violating the condition. So we have $14\cdot8!\cdot6!$ ways to arrange them in a circle, and the difference is $286\cdot8!\cdot6!$ Figuring out the $300$ and the $196$ in a nice way eludes me so far. Is this homework? If so for what course? – saulspatz Apr 21 '20 at 20:12
  • Technically this was ask on an online math contest that was held last week. – Willie Taylor Apr 21 '20 at 20:15

1 Answers1

1

In an online math contest, I assume it's legitimate to use a computer. Even so, it requires some analysis, because $14!$ is over $87$ billion, so you don't want to list all the permutations.

I approached it by counting all the permutations of $8$ B's and $6$ G's that don't have $3$ consecutive identical letters. I counted $300$ of these. Of course, each represents $6!\cdot8!$ permutations of the children.

In some of these permutations, we can close the line into a circle that obeys the condition, and in some we cannot. For example, if the line begins with $2$ boys and also ends with a boy, closing the circle would give $3$ boys in a row. I also counted how many lines could be closed into circles, and got $196$. That gives $196\cdot8!\cdot6!$, but since we're arranging the children in a circle, we have to divide by $14$ so we have only $14\cdot8!\cdot6!$ circular arrangements.

Finally the difference is $$(300-14)\cdot8!\cdot6!=8,302,694,400$$ so that we really didn't want to generate them.

The numbers are small enough that one could do it by hand, if for some reason that were necessary. There can must be at least $3$ groups of girls, and there can be at most $6$, where a group is a maximal set of adjacent persons of the same sex. There are at least $4$ groups of boys and at most $7$. (There can't be $8$ because $6$ girls cans separate the boys into at most $7$ groups.)

Suppose there are $3$ groups of girls. The only possible arrangement is BBGGBBGGBBGGBB, which gives $1$ line, and no circle.

Suppose there are $6$ groups of girls. There are at least $5$ groups of boys, so that leaves $3$ boys to dispose of. If we don't put any boys on the end, we must put $1$ boy in each of $3$ of the $5$ spots between the girls, giving $\binom53$. If we put a boy on one of the ends but not the other, we have $2\binom{5}{2}$ ways, since there are two ways to choose the ends. Or we could put $1$ boy on each end in $5$ ways. We could put $2$ boys on one end, and none on the other in $10$ ways. Finally, we could put $2$ boys on one end, and $1$ one the other in $2$ ways. Only these last $2$ ways can't be closed into a circle. If I haven't lost count, that's $47$ lines and $45$ circles.

I'll leave the cases or $4$ and $5$ girls to you, if you're interested.

saulspatz
  • 53,131