2
$\begingroup$

I just started studying basic combinatorics (as part of discrete mathematics for CS) and was given the following problem in a homework assignment. I believe I've solved it but I want to check my solutions:

$$\sim$$

Problem: Given a group of 10 adults, 40 girls, and 20 boys:

a) How many ways are there to arrange them in a line with the adults first, then the girls, then the boys?

b) How many ways are there to arrange them in a line with exactly six children between every two adults? (There may be children at either end of the line)

c) How many ways are there to arrange them in a line with exactly 4 girls and 2 boys between every two adults? (There may be children at either end of the line)

$$\sim$$

My solutions are as follows:

a) We have 10 spaces for the adults, then 40 spaces for the girls, then 20 spaces for the boys. So the answer is $10!\cdot40!\cdot20!$

b) For the "center" portion of the line (enclosed between the first and last adult): we have $10!$ ways to arrange the adults with 9 spaces in between then. The combined number of children is 60 and we want to get all the 54-tuples of them, so that's $\dfrac{60!}{6!}$, multiplied by all the ways to order 9 6-tuples of them: $9!$

For the ends we have 6 children left, so we want all the $6!$ possible ways to order them multiplied by the 7 ways the center portion of the line can be pushed between them.

So the final answer is

$$10! \cdot \dfrac{60!}{6!} \cdot 9! \cdot 6! \cdot 7 = 70 \cdot (9!)^2 \cdot 60!$$

c) In a similar fashion to the previous question, we'll address the center of the line first: $10!$ possible ways to arrange the adults. For each of these we'll take one of the $\dfrac{40!}{4!}$ 36-tuples of the girls and one of the $9!$ ways to arrange 9 4-tuples of them. For each of these we'll take one of the $\dfrac{20!}{2!}$ 18-tuples of the boys and one of the $9!$ ways to arrange 9 2-tuples of them. For each of these we'll pick 2 of the 5 spaces in the 4-tuple of girls to which they were assigned to "push" the two boys between the girls in the 4-tuple - there are $\dfrac{5!}{3!}$ ways to do this.

For the ends we have 6 children, so we want all the $6!$ ways to arrange them multiplied by all the 7 ways the center portion of the line may be pushed between them.

So the final answer is

$$ 10! \cdot \dfrac{40!}{4!} \cdot 9! \cdot \dfrac{20!}{2!} \cdot 9! \cdot \dfrac{5!}{3!} \cdot 6! \cdot 7 $$

$$ =70 \cdot (9!)^3 \cdot 6! \cdot \dfrac{40!\cdot20!\cdot5!}{4!\cdot3!\cdot2!} $$

$$\sim$$

This feels correct to me but since the numbers involved are so large, I don't really have any way to validate my solution. Even if I were to cut it down to 2 adults, 8 girls and 4 boys, the number of possibilities is much, much too great to check manually.

So I have two questions:

1) Are my answers correct and if not, why?

2) Generally speaking, is there a "simpler" method to approaching problems like this? Is/are there any way/s to validate the correctness of a solution without manually checking all the cases?

$\endgroup$

1 Answer 1

1
$\begingroup$

For the second part, there are $7$ possible patterns (in terms of which spaces have adults and which have children) for the line: there are exactly $54$ children between the first and last adult, so there are $6$ left over to go at the ends, any number form $0$ to $6$ of which can be at the left.

Once you've chosen a pattern, the adults can go in the $10$ adult spaces in any order, and the children can go in the $60$ child spaces in any order. So the answer is $7\times 60!\times 10!$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .