# Friends pairing problem

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!

• What's your question about it? Commented Jun 27, 2018 at 11:05
• Work it through for small $n$...$3,4$, say. I think it will become clear.
– lulu
Commented Jun 27, 2018 at 11:06
• How does it calculate the total pairs.. why is (n-1)*f(n-2) done? Commented Jun 27, 2018 at 11:08

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.
• @anupamD: Does it make sense now, or is there still a question? Commented Jun 27, 2018 at 11:40
• @Ufomammut: We case $f(n)$ based on the decision by person $n$. Either person $n$ decides to pair or person $n$ decides not to pair. Commented Jul 13, 2019 at 17:57
• @Ufomammut:$\;$Case $(1)$: Person $n$ decides to pair. Then there are $n-1$ choices for who person $n$ pairs with. If you now remove that pair from the room, you have $n-2$ people remaining, so $f(n-2)$ ways to complete the process. Hence, by the multiplication rule, the count for case $(1)$ is $(n-1)f(n-2)$. Commented Jul 13, 2019 at 17:57
• @Ufomammut:$\;$Case $(2)$: Person $n$ decides not to pair. If you now remove person $n$ from the room, you have $n-1$ people remaining, so $f(n-1)$ ways to complete the process. Commented Jul 13, 2019 at 17:57
• @Ufomammut: Since the cases are mutually exclusive, we sum the counts for the two cases, so $$f(n)=(n-1)f(n-2)+f(n-1)$$ Commented Jul 13, 2019 at 17:58

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.

• this explanation is pure gold :) Commented Jul 5, 2020 at 19:56

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