C++で集合の反射関係の数を求める方法

この記事では、C++を使って集合上に定義できる反射関係（reflexive relation）の総数を求める方法について解説します。問題設定としては、整数 n が与えられたとき、n 個の自然数からなる集合上に存在する反射関係の個数を求めるというものです。

反射関係とは

集合 A 上の関係 R が反射的であるとは、「A に属するすべての要素 a に対して、順序対 (a, a) が必ず R に含まれる」という条件を満たすことを意味します。数式で表すと次のようになります。

(a, a) ∈ R （∀ a ∈ A）

具体的な入出力の例を見てみましょう。

入力 : x = 1
出力 : 1
説明 : 集合 = { 1 } のとき、A × A 上の反射関係 :
{ { 1 } }

入力 : x = 2
出力 : 4
説明 : 集合 = { 1, 2 } のとき、A × A 上の反射関係 :
　　{ ( 1, 1 ), ( 2, 2 ) }
　　{ ( 1, 1 ), ( 2, 2 ), ( 1, 2 ) }
　　{ ( 1, 1 ), ( 2, 2 ), ( 1, 2 ), ( 2, 1 ) }
　　{ ( 1, 1 ), ( 2, 2 ), ( 2, 1 ) }

解法の考え方

n 要素の集合上の反射関係の数は、次の公式で求められます。

2^n²−n

この公式が成り立つ理由は以下の通りです。反射関係では、対角成分にあたる n 個の順序対 (a, a) は必ず含まれていなければなりません。一方、それ以外の n² − n 個の非対角ペアについては、それぞれ「関係に含めるかどうか」を自由に選ぶことができます。各ペアに2通りの選択肢があるため、全体で 2^n²−n 通りの反射関係が存在することになります。

C++での実装例

#include <iostream>
using namespace std;
int countReflexive(int n){
    int ans = 1 << (n*n - n);
    return ans;
}
int main(){
    int n ;
    cin >> n ; // 標準入力から n を受け取る
    int result = countReflexive(n); // 反射関係の数を計算する関数を呼び出し
    cout << \"Number of reflexive relations on set: \" << result ; // 結果を出力
    return 0;
}

出力結果

Number of reflexive relations on set: 1

プログラムの解説

このプログラムの流れは非常にシンプルです。ユーザーから n を入力として受け取り、公式 2^n²−n を計算しているだけです。2 のべき乗の計算にはビット左シフト演算子「<<」を使用しており、これにより高速に値を求められます。時間計算量は O(1) です。ただし、int 型で表現できる範囲には限りがあるため、n が大きくなるとオーバーフローを起こす点には注意が必要です。より大きな n を扱いたい場合は、long long 型や多倍長整数型の利用を検討するとよいでしょう。

まとめ

この記事では、集合上の反射関係の数を求める問題を取り上げました。数学者によって導き出された公式 2^n²−n を利用することで、複雑な全列挙を行わずとも非常にシンプルに答えを計算できることを確認しました。また、C++による実装例を通じて、O(1) の時間計算量で解を得る方法を学びました。同じロジックは C、Java、Python など他の言語でも同様に実装可能です。