Tìm số lượng quan hệ tự phản xạ trên tập hợp bằng C++

Cho số n, tập hợp A = {1, 2, ..., n}. Quan hệ tự phản xạ (reflexive relation) trên A là quan hệ R ⊆ A × A sao cho (a, a) ∈ R với mọi a ∈ A. Tìm số lượng quan hệ như vậy.

Ví dụ

Input: x = 1 Output: 1
Tập {1}, quan hệ: {(1,1)}

Input: x = 2 Output: 4
Tập {1,2}, các quan hệ:
{(1,1),(2,2)}, {(1,1),(2,2),(1,2)}, {(1,1),(2,2),(1,2),(2,1)}, {(1,1),(2,2),(2,1)}

Công thức toán học

Tổng số cặp trong A × A là n². Trong đó n cặp đối chéo (a,a) bắt buộc phải có. Các n² - n cặp còn lại có thể chọn hoặc không chọn tùy ý. Số quan hệ = 2^(n² - n).

Mã nguồn C++

#include <iostream>
using namespace std;

int countReflexive(int n) {
    int ans = 1 << (n * n - n); // 2^(n^2 - n)
    return ans;
}

int main() {
    int n;
    cin >> n;
    int result = countReflexive(n);
    cout << "Số quan hệ tự phản xạ: " << result;
    return 0;
}

Kết quả

Số quan hệ tự phản xạ: 1

Giải thích

Sử dụng phép dịch bit trái 1 << k để tính 2^k. Độ phức tạp O(1). Lưu ý: với n lớn, kết quả vượt quá kiểu int, cần dùng big integer hoặc modulo.

Kết luận

Bài viết trình bày công thức tính số quan hệ tự phản xạ: 2^(n²-n). Mã nguồn C++ đơn giản sử dụng phép dịch bit. Có thể triển khai bằng các ngôn ngữ khác.