C++ Số cách ghép cặp mọi người

Cho n người, mỗi người hoặc đơn độc hoặc ghép cặp. Tìm số cách ghép cặp. Ví dụ:

Input: 3 → Output: 4
Cách: {1}{2}{3}, {1,2}{3}, {1}{2,3}, {1,3}{2}

Input: 6 → Output: 76

Phương pháp giải

Dùng công thức Young Tableau: A[n] = A[n-1] + (n-1) × A[n-2]. Với A[1]=1, A[2]=2.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int Young_Tableau(int n) {
    int A[n+1];
    A[1] = 1; A[2] = 2;
    for (int i=3; i<=n; i++)
        A[i] = A[i-1] + (i-1) * A[i-2];
    return A[n];
}

int main() {
    int n = 6;
    cout << Young_Tableau(n);
    return 0;
}

Kết quả

76

Giải thích

Công thức đệ quy: người thứ n hoặc đứng một mình (A[n-1] cách) hoặc ghép với 1 trong (n-1) người còn lại, phần còn lại A[n-2] cách.

Kết luận

Đã giải bài toán số cách ghép cặp bằng công thức Young Tableau O(n). Code C++ áp dụng cho C, Java, Python. Hy vọng hữu ích.