6
$\begingroup$

In how many ways can $7$ girls and $3$ boys sit on a bench in such a way that every boy sits next to at least one girl

The answer is supposedly $1,693,440 + 423,360 = 2,116,800$

$\endgroup$
  • 1
    $\begingroup$ Dear user157220: If you find answers helpful, you can upvote each of them. If you find one answer to be most helpful, you can also accept the answer. To accept an answer, just click on the grey $\large \checkmark$ to the left of the answer you'd like to accept. It turns green when you click on it, and you get $2$ reputation points for each answer you can accept. (You can accept only one answer per question asked.) $\endgroup$ – Namaste Jun 17 '14 at 12:24
  • $\begingroup$ Boy should sit next to a girl means, the arrangement should not read ''BB" and should not begin with Boy. Am I right? $\endgroup$ – Chellapillai Jun 18 '14 at 11:20
6
$\begingroup$

$7$ girls can be seated in $7!=5040$ ways. Each seating creates six inner slots where one or two boys can be placed, and two end slots where at most one boy can be placed.

When no two boys shall sit together we can place them in $8\cdot 7\cdot6=336$ ways in the eight slots ($8$ choices for the first boy, $7$ remaining for the second, and $6$ for the third).

When two boys shall sit together we can choose any of the $6$ inner slots for them. Then we can pick the lefthand one of the two in $3$ ways, the righthand one in $2$ ways. Finally we can choose any of the $7$ leftover slots for the third boy. In all we have $6\cdot3\cdot2\cdot 7=252$ possibilities for such an arrangement.

It follows that the total number of admissible seatings is given by $$5040\cdot(336+252)=2\,963\,520\ .$$

$\endgroup$
  • $\begingroup$ Very Nice solution. simple and easy to undersand. Thanks $\endgroup$ – Satish Ramanathan Jun 17 '14 at 8:18
  • $\begingroup$ The sequence shouldn't begin with $GB$, isn't it? $\endgroup$ – Chellapillai Jun 18 '14 at 11:26
  • $\begingroup$ @Chellapillai: The sequence may begin with $GBG\ldots$, $GBBG\ldots$, $BG\ldots$, but not with $BBG\ldots$. $\endgroup$ – Christian Blatter Jun 18 '14 at 16:18
  • $\begingroup$ I am sorry. I made a mistake in my previous comment. Please help me to correct my misunderstanding."Every Boy should sit next to a Girl means" what? It should be like this ...GB...GB... GB.... Therefore it shouldn't begin with BG and "BB" shouldn't occur anywhere in the sequence. Am I right? $\endgroup$ – Chellapillai Jun 19 '14 at 2:03
  • $\begingroup$ Okay I think I have to understand in this way.The neighbour of each boy should contain at least one girl. In practice,the word "next" means it will consider only one direction, isn't it? $\endgroup$ – Chellapillai Jun 19 '14 at 2:29
4
$\begingroup$

Hint: Consider the complement, which is "there is a boy who sits between two boys OR there is a boy at the end of the line who is next to a boy".

There are 10! ways to arrange without restriction.

There are $ 3! \times 8!$ ways to arrange BBB as a block.

There are $3! \times 8! \times 2$ ways to arrange BB as a block at either end.

There are $ 3! \times 7! \times 2$ ways to arrange BBB as a block at either end.

$\endgroup$
  • $\begingroup$ So are you saying that if I eliminate these. The rest should be the answer $\endgroup$ – StephanCasey Jun 15 '14 at 16:20
  • $\begingroup$ @user157220 Yes. You'd have to use PIE, since the sets overlap. $\endgroup$ – Calvin Lin Jun 15 '14 at 16:23
  • $\begingroup$ Excuse my stupidity but what is PIE $\endgroup$ – StephanCasey Jun 15 '14 at 16:30
  • $\begingroup$ @user157220 It is the Principle of Inclusion and Exclusion. $\endgroup$ – Calvin Lin Jun 15 '14 at 16:31
  • $\begingroup$ Okay. That's what I thought. I just didn't know exactly PIE but I do know about inclusion and exclusion. Please shed some insight on how to solve the problem further though. I don't know what will be included and how to make sure I don't exclude things more than once $\endgroup$ – StephanCasey Jun 15 '14 at 16:33
4
$\begingroup$

We can also solve it using a two variable recursion:

Let $A(b,g)$ be the number of ways of arranging the string of B's and G's, such that it does not contain ``BBB'' as a substring. It can be written as:

\begin{align*} A(b,g) &= A(b,g-1)+A(b-1,g-1)+A(b-2,g-1) \\ A(0,g) &= 1 \\ A(1,g) &= 1+g \\ A(2,g) &= \binom{2+g}{2} \\ A(b,0) &= 0 \end{align*} Since we also need a condition that it cannot begin with "BBG'' or end with "GBB'', the number of valid strings (by PIE) are $$A(m,n)-2\, A(m-2,n-1)+A(m-4,n-2)$$ where $m$ and $n$ are the number of boys and girls, respectively.

Since B's and G's are distinguishable, the total number of possible ways are

$$\mathbb{N}\left(m,n\right) = \Big(A(m,n)-2\, A(m-2,n-1)+A(m-4,n-2)\Big)\cdot m!\cdot n!$$

And for our problem, $\mathbb{N}(3,7) = 98\cdot 3!\cdot 7! = 2963520$

Update

We can get a generating function, from its regular expression (obtained by building a deterministic finite automaton and minimizing it), as described in analytic combinatorics

The RE is $((g+bg)g^*b)^*(\epsilon+(g+bg)g^*)$ and the g.f. obtained will be: \begin{align*} G(x,y) &= \mathrm{SEQ}\left(\left(y+xy\right)\mathrm{SEQ}(y)x\right)\left(1+(y+xy)\mathrm{SEQ}(y)\right) \\ &= \mathrm{SEQ}\left(\frac{y+xy}{1-y} x\right)\left(1+\frac{y+xy}{1-y}\right) \\ &= \frac{1+xy}{1-y(1+x+x^2)} \end{align*}

Update 2

From the g.f, we can also get the following formula:

\begin{align*} \mathbb{N}(m,n) &= \left(\sum_{k=\lfloor m/2 \rfloor}^m \binom{n-1}{k}\binom{k}{m-k-1} + \binom{n}{k}\binom{k}{m-k}\right)\cdot m! \cdot n! \end{align*}

$\endgroup$
  • $\begingroup$ Thanks for confirming that the answer was correct. I'm sure I will learn this method later on in my course $\endgroup$ – StephanCasey Jun 16 '14 at 12:56
  • $\begingroup$ You're welcome. I can't say about your course, though. Nevertheless, it's interesting to me. Nice problem for a recursion! $\endgroup$ – gar Jun 16 '14 at 13:11
  • $\begingroup$ Alright that's good :) I'm glad you found it interesting. Well I'm studying Actuarial Science in South Africa with a double major in mathematical statistics so I'm halfway through first year stats and we've only really spent a few weeks on permutations and combinations plus a little bit of probability theory so I'd expect to go a bit deeper into some more interesting stuff further on. The rest of the time we were doing descriptive stats etc. $\endgroup$ – StephanCasey Jun 16 '14 at 13:18
  • $\begingroup$ I see. It's particularly useful to be programmed in a computer, makes solutions very short, at the expense of time to execute it. Enjoy your course! $\endgroup$ – gar Jun 16 '14 at 13:28
  • $\begingroup$ Also the sequence shouldn't begin with $GB$ and $BB$ shouldn't occur in arrangement, isn't it? $\endgroup$ – Chellapillai Jun 18 '14 at 11:23
1
$\begingroup$

I think I've got an answer. Please tell me if you see any fault with it.

A method of subtracting the impossible cases seemed to be the best but I no longer think so. However. The answer they gave seems wrong either way.

So working with the cases that are possible it's either

B B B

G G G G G G G

OR

BB B

G G G G G G G

In the first case, all the boys are separated. They must fill one slot either between two girls or on the end each. All of these cases are valid

$7! \times {^8\mathrm{P}_3} = 1 693 440$

In the second case, there is a group of 2 boys and one boy on its own that need to be sorted. The group of 2 CANNOT be on either end so only the spaces in between the girls is valid where the last boy can occupy any space including the ones on the end EXCEPT the one where the group of two occupied a space

$7! \times {^3\mathrm{P}_2} \times {^6\mathrm{P}_1} \times {^7\mathrm{P}_1} = 1 270 080$

$\begin{align}\operatorname{n}(S) &= 1 693 440 + 1 270 080 \\ & = 2 963 520\end{align}$

                        --------------->

Please tell me if you think I've made a false assumption or worked something out incorrectly

$\endgroup$
  • $\begingroup$ The second case should be: ${^7\mathrm{P}_7}\times {^3\mathrm{P}_3} \times {^6\mathrm{C}_1} \times {^7\mathrm{C}_1} = 1270080$; correct value, wrong logic. Count the ways to order all the girls, order all the boys, and select places to put the boys between the girls. $\endgroup$ – Graham Kemp Jun 16 '14 at 13:50
  • $\begingroup$ Oh okay I see your logic but what I did was order the group of two boys then use permutations to place the boys and order them $\endgroup$ – StephanCasey Jun 16 '14 at 14:00
  • $\begingroup$ Is it not correct logic in the first step to say 7P7 x 8P3 AND 7P7 x 8C3 x 3!. I assumed that the permutations method just orders it already $\endgroup$ – StephanCasey Jun 16 '14 at 14:02
  • $\begingroup$ Indeed, @user157220 , $\newcommand{\P}[2]{\,{^{#1}\mathrm{P}_{#2}}\,} \newcommand{\C}[2]{\,{^{#1}\mathrm{C}_{#2}}\,} \P83=\C83\times 3!$. Both expressions are equivalent ways to count: selecting 3 of 8 places and arrange 3 boys in those places. The difference starts to show if you were doing this for 4, or more, boys. For four boys, this should be: $\newcommand{\P}[2]{\,{^{#1}\mathrm{P}_{#2}}\,} \newcommand{\C}[2]{\,{^{#1}\mathrm{C}_{#2}}\,} \P77 \P44 (\C84 + \C61 \C72 + \C62)$ $\endgroup$ – Graham Kemp Jun 17 '14 at 0:25
1
$\begingroup$

This problem is tantamount to making the arrangements with consecutive boys sitting amongst girls. The total number of ways 3 boys and 7 girls could be arranged is 10! ways. Of these, the number of ways boys sit with girls can be broken down into three cases.

  1. BBB and 7 girls
  2. BB, B, and 7 girls
  3. B,B,B and 7 girls.

We can consider the first cast to have two pairs, the second case to have one pair and the third case to have no pairs. The summation of the number of ways on all three cases should equal 10!. In the question asked, we do not want the first one because, there happens to be a two consecutive pairs of boys sitting violating the rule. What we do not want of the second are those that start with BBG and those that end with GBB.

BBG _ _ _ _ _ _ _. This could be arranged in ${3\choose2}{7\choose1}2!7!$

Similarly _ _ _ _ _ _ _GBB. This could be arranged in ${3\choose2}{7\choose1}2!7!$

Summing these two, we get $14*3!*7!$.

Atlast what we want is the third case when there are no pairs and each boy is sitting with girls Let us call $n_1$ = no of girls and $n_2$ = no of boys

Each pair must have a left-hand member, which we can choose from any of the boys except the last one : $\tbinom{n_2-1}{p}$. This will create $n_2-p$ blocks of boys, which we can distribute into the $n_1+1$ slots between and around the girls: $\tbinom{n_1+1}{n_2-p}$. Thus the number of ways with exactly $p$ pairs is $\tbinom{n_2-1}{p}\tbinom{n_1+1}{n_2-p}$.

For p = 2: $\tbinom{3-1}{2}\tbinom{7+1}{3-2} = 8$ and this you multiply by 3! to arrange boys and 7! ways to arrange girls.

We do not want any of the above.

For p = 1:$\tbinom{3-1}{1}\tbinom{7+1}{3-1} = 2*28*3!*7! = 56*3!*7!$

Now subtract what we do not want in one pair which is $14*3!7!$

What we want from p = 1 is $(56-14)*3!*7! = 42*3!*7!$

For p = 0:$\tbinom{3-1}{0}\tbinom{7+1}{3-0} = 56 = 56*3!*7!$

What we want from p = 0 is all and thus the number of ways $ = 56*3!*7! = 1693440$

The total number of ways such that all boys sit with atleast one girl $=(56+42)*3!*7! = 98*3!*7!$ = 2963520.

$\endgroup$
  • $\begingroup$ "Every Boy should sit next to a Girl means" what? It should be like this ...GB...GB... GB.... Therefore it shouldn't begin with BG and "BB" shouldn't occur anywhere in the sequence, isn't? $\endgroup$ – Chellapillai Jun 19 '14 at 2:08
  • $\begingroup$ It could be to the left or right. So BG is a proper way. BB is a proper way as long as it is not to the either end, Because, GBBG is admissible as The boys are sitting next to a girl. I think you have to go read the solutions of others and make sense out of it. $\endgroup$ – Satish Ramanathan Jun 19 '14 at 2:14
  • $\begingroup$ Thank you. Therefore the question should be in this way. The neighbour of each boy should contain at least one girl. In practice,the word "next" means it will consider only one direction, isn't it? $\endgroup$ – Chellapillai Jun 19 '14 at 2:22
  • $\begingroup$ No 'Next' could mean to the right or left. Are you a student? $\endgroup$ – Satish Ramanathan Jun 19 '14 at 2:24
  • $\begingroup$ I am soory. What is the number next to 3? $\endgroup$ – Chellapillai Jun 19 '14 at 2:36
1
$\begingroup$

Answer: $7\times 6\times 5\times7!=1058400$

Proof: First I count, in how many ways we can form a set $\{g_ib_j,g_kb_l,g_mb_n\}$?. This is equal to the number of one-one maps form the set $\{B_1,B_2,B_3\}$ to the set $\{g_1,g_2,g_3,g_4,g_5,g_6,g_7\}$. It is equal to $7\times 6\times 5$.

And for each set $\{g_ib_j,g_kb_l,g_mb_n\}$, there are $7!$ arrangements such that each boy is sitting next to at least one girl. It follows from the fact that we have three elements $g_ib_j,g_kb_l,g_mb_n$ and $4$ remaining girls. Since there are $7\times 6\times 5$ sets of the form $\{g_ib_j,g_kb_l,g_mb_n\}$, total number of elements is equal to $7\times 6\times 5\times7!=1058400$

Please help me to count the elements which are escaping from my counting.

$\endgroup$

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.