友達ペアリングの問題

グループには、n人の友達がいます。一人一人が独身のままでいることも、他の友達とペアになることもできます。友達が独身のままでいることも、ペアになることもできる方法の総数を見つけましょう。

1つのペアに2人の友人のpとqがある場合、（p、q）または（q、p）は同じです。

n人の友人のグループの場合、f（n）を、ペアにする方法または単一のままにする方法の数とします。次に、n番目の人が独身のままであるか、ペアになっています。 n人目が独身の場合、（n-1）人の友達を繰り返します。 n番目の人が残りの（n-1）人のいずれかとペアになっている場合、（n-1）* f（n-2）を繰り返します。

入力と出力

Input:
The number of friends. Say 5.
Output:
The possible way to pair them. Here the answer is 26.

アルゴリズム

countPairs(n)

入力： 友達の数。

出力 ：n人の友達をペアリングする方法の数。

Begin
   define pair array of size n + 1
   pair[0] := 0, pair[1] := 1 and pair[2] := 2

   for i in range 3 to n, do
      pair[i] := pair[i-1] + (i+1)*pairs[i-2]
   done

   pair[n]
End

例

#include <iostream>
using namespace std;

int countPairs(int n) {
   int pairs[n + 1];             //number of pairs for ith number

   //for number 0 to 2, there are 0 to 2 possible combination
   pairs[0] = 0;
   pairs[1] = 1;
   pairs[2] = 2;

   for (int i = 3; i <= n; i++)             //fill array for 3 to n numbers
      pairs[i] = pairs[i-1] + (i-1) * pairs[i-2];

   return pairs[n];
}

int main() {
   int n;
   cout << "Enter numbers: "; cin >> n;
   cout << "Number of ways to pair "<<n<<" friends: " << countPairs(n);
}

出力

Enter numbers: 5
Number of ways to pair 5 friends: 26