How Many Pairing Options Exist at a Party with 2n People?

[anemone]

1. How many ways are there of pairing $2n$ people at a party?

2. Suppose Mark arrives late to the party. Suppose everyone is repaired (inevitable leaving one person alone). How many possible parings are there now?

---

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Congratulations to lfdahl for his correct solution. :)

Here's lfdahl's solution:

Spoiler

a. $P(2n)$ denotes the number of pairings of $2n$ people.

A table of $P(2n)$-values can be made by decomposition:

$n = 1$: Two persons. Obviously: $P(2) = 1$.

$n = 2$: Four persons $\left \{ 1,2,3,4 \right \}$ make up two pairs: Person no. $1$ can be paired in $2n-1 = 3$ ways. Once $1$ is paired with one of the other $3$ there are only $2$ persons left, so $P(4) = 3 \cdot P(2) = 3 \cdot 1 = 3$.

$n = 3$: Six persons $\left \{ 1,2,3,4 ,5,6\right \}$ make up three pairs: Person no. $1$ can be paired in $2n-1 = 5$ ways. Once $1$ is paired with one of the other $5$ there are $4$ persons left, so $P(6) = 5 \cdot P(4) = 5 \cdot 3 \cdot 1 = 15$.

Thus the decomposition has the general form: $P(2n) = (2n-1) \cdot P(2n-2)$, $n \ge 2$.

Consequently: $P(2n) = (2n-1) \cdot (2n-3) \cdot (2n-5) … 5 \cdot 3 \cdot 1 = (2n-1)! $

b. When Mark arrives later, there are $2n+1$ persons, i.e. there are $2n+1$ ways of excluding one person
when making $P(2n)$ pairings. Thus, the number of possible pairings is:

$(2n+1) \cdot P(2n) = (2n+1) \cdot (2n-1) \cdot (2n-3) … 5 \cdot 3 \cdot 1 = (2n+1)! $