Problem :
There are n people in a party. Each person can either join dance as a single individual or as a pair with any other. Find the number of different ways in which all n people can join the dance.
Input data One integer n (1 ≤ n ≤ 10^5).
Output data Print the number of different ways in which all n people can join the dance. Print the answer modulo 10^9 + 7.
Let we have n = 3 people. They can dance in 4 ways: {1, 2, 3}, {{1, 2}, 3}, {1, {2, 3}}, {{1, 3}, 2}.
If question is easy, Sorry.
I think answer equivalent with number of pairs in party :
I divide problem to 3 parts:
All are single in party .--> +1
There is only one pair --> n * (n - 1) / 2
Other cases that are some pairs --> I need help here.
answer = n * (n - 1) / 2 + Other cases + 1
I calculated these:
n = 3 : 3 + 0 + 1;
n = 4: 6 + 3 + 1;
n = 5: 10 + 15 + 1 ;
n = 6: 15 + 15 + 1;
If I understand your question correctly, there is also a direct counting argument.
Think about how many ways there are to form $k$ pairs. Note that $k$ must be between $0$ and $\left\lfloor \frac{n}{2} \right\rfloor$, inclusive. For the first pair, there are $n$ choices for the first person and $n - 1$ choices for the second person. However, we don't care which person is "first" and "second", just that they are a pair. So that gives $\frac{n (n - 1)}{2}$ ways to form the first pair. Forming subsequent pairs is equally easy. For the $m$th pair, there are $n - 2 m + 2$ people from which to pick. So, there are $\frac{(n - 2 m + 2) (n - 2 m + 1)}{2}$ ways to select the pair.
However, just as we don't care which person is "first" in a pair, we also don't care about the order in which the pairs are formed. So, we will divide the product by $k!$.
The result is
$$\sum_{k = 0}^{\left\lfloor \frac{n}{2} \right\rfloor} \frac{1}{k! 2^k} \frac{n!}{(n - 2 k)!}$$