0

In a village, there are 10 boys and 10 girls. The village matchmaker arranges all the marriages. In how many ways can she pair off the 20 children, if homosexual marriages (male-male or female-female) as well as heterosexual marriages are allowed?

My original answer was $\binom{20}{2}$, which turns out to be wrong and the correct answer is $19\cdot 17 \cdot 15 \cdots 1$. But I couldn't understand why my solution is wrong and why the correct answer is indeed correct, please helps.

In fact, Combinatorics and Probability are my weakest areas of math, can anybody recommend good textbooks on them, thank you.

Jessie
  • 343
  • 5
    It seems the matchmaker is still rather traditional, excluding threesomes, foursomes, and so on. Your $\binom{20}{2}$$ counts the number of ways to arrange a single marriage. – André Nicolas Jul 03 '15 at 15:38
  • Child marriages? – Henry Jul 03 '15 at 16:14
  • 1
    This answer contains two explanations of the correct answer in the general case of $n$ boys and $n$ girls. $\binom{20}2$ is wrong because it’s simply the number of ways to choose one pair of children. That pair could be a boy and a girl, two boys, or two girls, and in any case there are still $9$ more pairs to be formed. – Brian M. Scott Jul 03 '15 at 20:10

3 Answers3

3

Arrange the 20 children in a row from left to right. The first child has 19 choices for marriage.

Remove the first child and the first child's spouse, and there are 18 children left. The leftmost child of these 18 has 17 choices.

Now remove him and his spouse, and there are 16 children left. The leftmost child of these 16 has 15 choices.

Continue this way. Eventually there will be two children left, and there is one way to pair them together.

By the multiplication principle, the total number of ways is $19*17*...*1$.

n55
  • 1,563
0

Amongst twenty people, fix one and there $19$ people for the person to marry. Delete this couple from set and fix one person, there are now $17$ people for that person to choose from. Delete this couple from the set. There are now $16$ people in consideration. Fix one, and there are $15$ choices for the persons spouse. Continue like this till were are only two people remaining and there is only one way to pair them off.

Hence the total number of ways is $$19 \cdot 17 \cdot 15 \cdots 1$$

Zain Patel
  • 16,802
0

What if $k$ of the children weren't heterosexual?

Anyway, arrange the $20$ children randomly in a line, there are $20!$ ways to do this. Starting with the leftmost, pair each alternate child to their right neighbour. Imagine these pairs as individual items. Rearranging them doesn't change the marriage, so divide by $10!$. And each marriage has $2$ representations ($xy$ and $yx$), so divide by $2^{10}$.

For example, on $n=4$, $1234=2134=1243=2143=3412=4312=3421=4321$, so there are only $3$ distinct permutations, and:

$$ \dfrac{(2n)!}{n!2^n}=\dfrac{4!}{2!4}=\dfrac{24}{8}=3$$

JMP
  • 21,771