1からnまでの自然数で構成される集合の全部分集合の合計を求める

集合（セット）とは、複数のデータ要素をひとまとめに扱うための概念です。そして、ある集合 A の部分集合 B とは、B に含まれるすべての要素が A にも存在するような集合を指します。

この記事では、「1 から n までの連続する自然数」で構成される集合を対象に、そのすべての部分集合に含まれる数値の総和を求める方法を解説します。基本的な考え方は、生成可能なすべての部分集合を列挙し、そこに現れる数値をすべて足し合わせるというものです。

具体例で確認する

まずは小さな例で考えてみましょう。

N = 3
集合     = {1, 2, 3}
部分集合 = {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

各部分集合の要素をすべて加算すると、

1 + 2 + 3 + (1+2) + (1+3) + (2+3) + (1+2+3)
= 1 + 2 + 3 + 3 + 4 + 5 + 6
= 24

なお、空集合 ∅ も厳密には部分集合ですが、合計が 0 であるため結果には影響しません。

規則性を見つけて公式を導出する

答えを要素ごとに整理すると、興味深い規則が見えてきます。

「1」は 4 回、「2」は 4 回、「3」も 4 回登場しています。つまり、
合計 = 4 × (1 + 2 + 3) = 4 × 6 = 24

これは偶然ではありません。n 個の要素からなる集合において、ある特定の 1 要素に注目すると、その要素を含む部分集合の数は「残りの n−1 個の要素から自由に選ぶ組み合わせの数」、すなわち 2^(n−1) 通りに等しくなります。

したがって、求める合計 S は次の閉じた形式（公式）で表せます。

S = 2^(n−1) × (1 + 2 + … + n) = 2^(n−1) × n(n+1) / 2

n = 3 の場合に当てはめると、2² × 3×4/2 = 4 × 6 = 24 となり、先ほどの結果と一致します。この公式を使えば、部分集合を実際に列挙することなく答えを直接計算できます。

C言語での実装例

べき乗の計算には繰り返し二乗法を用いることで、全体の計算量を O(log n) に抑えられます。また、n が大きくなると答えは非常に巨大になるため、競技プログラミングなどでは一般的に 10⁹+7 で割った余りを求めます。以下はその実装例です。

#include <stdio.h>
#define MOD 1000000007LL

/* 繰り返し二乗法により x^y を MOD で割った余りを求める */
long long power(long long x, long long y) {
    long long res = 1;
    x %= MOD;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return res;
}

int main(void) {
    int n = 45;

    /* 1 + 2 + … + n を先に計算しておく（必ず整数になるため安全） */
    long long sum = (long long)n * (n + 1) / 2 % MOD;

    /* 各要素は 2^(n-1) 個の部分集合に現れる */
    long long ans = sum * power(2, n - 1) % MOD;

    printf("部分集合の合計は %lld\n", ans);
    return 0;
}

出力

部分集合の合計は 428515176

まとめ

• n 個の要素からなる集合では、各要素はちょうど 2^(n−1) 個の部分集合に含まれる
• そのため全部分集合の合計は 2^(n−1) × n(n+1)/2 のひとつの式で求められる
• 繰り返し二乗法を使えば O(log n) で計算でき、mod を取れば巨大な n にも対応できる