Friends pairing problem

Question

I came across this question:

Given $n$ friends, each one can remain single or can be paired up with some other friend. Each friend can be paired only once. Find out the total number of ways in which friends can remain single or can be paired up.

The recursive solution for this problem is:

Let $f(n)$ be the number of ways $n$ people can remain single or pair up. Then, $$f(n) = f(n - 1) + (n - 1) * f(n - 2)$$

For the $n$-th person there are two choices:

1. the $n$-th person remains single, we recur for $f(n - 1)$
2. the $n$-th person pairs up with any of the remaining $n - 1$ persons. We get $(n - 1) * f(n - 2)$

Can anyone please elaborate this solution. Thanks!

Answer 1

Label the people as $1,...,n$.

If person $n$ pairs with someone, there are $n-1$ possibilities for the person who pairs with person $n$, and once that pair is specified, we have $n-2$ people left, with the same counting problem, but with $2$ less people, so for this case, the number of ways is $(n-1)f(n-2)$.

If person $n$ stays single, then we have $n-1$ people left, with the same counting problem, but with $1$ less person, so for this case, the number of ways is $f(n-1)$.

Hence we have the recursion $$f(n)=(n-1)f(n-2)+f(n-1)$$ for $n\ge 2$, together with the initial conditions $f(0)=f(1)=1$.

Notes:

• $f(n)$ is not counting "total pairs", but rather, the number of possible outcomes, including who pairs with who, and who stays single.$\\[4pt]$
• The outcomes where person $n$ is paired are distinct from the outcomes where person $n$ is not paired, so what happens to person $n$ effectively splits the problem into two cases. Thus, to count all possible outcomes, we need to sum the counts for each case.
• For the case where person $n$ pairs, as already mentioned, there are $n-1$ possibilities for how to form the pair, but regardless of who pairs with person $n$, the number of ways to complete it to a full outcome is $f(n-2)$, so the multiplication rule applies.

Answer 2

Let $P_n$ be the set of all possible (partial) pairings of $n$ people.

To count the number of elements in $P_n$, you pick a fixed person, lets say Tom, and then divide the set $P_n$ of all pairings of the $n$ people into two disjoint subsets: the set $A_n$ of all pairings where Tom remains single and the set $B_n$ of all pairings where Tom gets hooked up.

For $A_n$ we have $|A_n|=|P_{n-1}|$, since when Tom stays single we just have to (partially pair) all the others. For $B_n$ Tom gets hooked up with one of the $n-1$ other persons, and for each of those choices we have to pair up the remaining $n-2$ people, so that $$|B_n| = (n-1)\cdot|P_{n-2}|.$$

In conclusion $$ |P_n| = |A_n \cup B_n| = |A_n| + |B_n| = |P_{n-1}| + (n-1) |P_{n-2}|. $$

Answer 3

I guess, the main problem which I also faced was $(n-1)$*$f(n-2)$ part of the equation.

So instead consider the order $f(n-2)$*$(n-1)$.

This can be rewritten as $f(n-2)$ + $f(n-2)$ + $f(n-2)$ + $...$ $(n-1)$ times. This will be helpful afterwards

Now let's derive the recursive formula with following cases:

1. $n^{th}$ guy is single
2. $n^{th}$ guy gets paired up.

So the recursion will look something like this $f(n)$ = $f(n-1)$ + $f(n-2)$

This says if the guy is single, the problem remains the same for $(n-1)$ people or if the guy is paired up with anyone, problem remains same for $(n-2)$ people (because 2 people are now let's say gone). But heres a thing which I think is better understood with an example.

for $n = 4$ and $\{A,B,C,D\}$ as there names :

1. guy D chose to be single, people left : ${A,B,C}$
2. guy D gets paired up.

Pairing options are :

$(A)$, $(B,C)$

$(A,B)$,$(C)$

$(A,C)$, $(B)$

So we can say:

$f(n)$ = $f(n-1)$(if guy stays single) + $f(n-2)$(if first pair is formed) + $f(n-2)$(if second pair is formed) + $f(n-2)$(if third pair is formed).

So in essence, each pair contributes to the total, finally:

$f(n)$ = $f(n-1)$ + $f(n-2)$*$(n-1)$

$(n-1)$ = no. of ways $n$ can form a pair with $n-1$ people.