Friends pairing problem

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.

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 question remains the same for $(n-1)$ people or if the guy is paired up with anyone, question remain 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.

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