2
$\begingroup$

Question: Suppose there are m girls and n boys in a class. What is the number of ways of arranging them in a line so that all the girls are together? (Biggs, Discrete Mathematics 2nd ed, Exercise 10.7.5)

My solution

Say $m=4$ and $n=3$

The number of ways they can be arranged are:

G - a girl, B - a boy

position 1: [G G G G][B B B]
position 2: [B][G G G G][B B]
position 3: [B B][G G G G][B]
position 4: [B B B][G G G G]

So in this case the group of girls can be placed in $4$ different positions. On each position the group of girls can internally be arranged in $4!$ different ways, and the boys can be arranged in $3!$ different ways.

Hence the total number of arrangements are $4!*3!*4$

Converting the answer back to variables, I end up with: $m!*n!*(n + 1)$

The book provides no solution, so I would really like to know if I came up with the right answer..

$\endgroup$
  • 2
    $\begingroup$ It's not really a set theory question. $\endgroup$ – tomasz Aug 8 '12 at 18:39
  • 1
    $\begingroup$ Note that $n!(n+1)=(n+1)!$ $\endgroup$ – celtschk Aug 8 '12 at 18:41
  • $\begingroup$ sorry my bad, the chapter was all about sets and permutations, just presumed set theory $\endgroup$ – hampusohlsson Aug 8 '12 at 18:42
  • $\begingroup$ @tomasz what category would you suggest? $\endgroup$ – hampusohlsson Aug 8 '12 at 18:46
  • $\begingroup$ Your answer is correct. One way to argue it for general $m$ and $n$ is that we can have $0$ or $1$ or $2$ or $\dots$ $n$ boys to the left of the clump of girls, so $n+1$ choices. Multiply $n+1$ by $m!n!$ to account for ordering. There is a cuter argument that gets you an answer of $(n+1)!m!$ directly. $\endgroup$ – André Nicolas Aug 8 '12 at 18:47
0
$\begingroup$

The basic idea and the answer are correct, but for a complete solution, you should show it in abstract context, so start with arbitrary (unspecified) $m,n$ and try to show that you get $(n+1)!m!$ as a result.

$\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.