Problem 553 のバックアップの現在との差分(No.1)

• バックアップ一覧
• 差分 を表示
• ソース を表示
• バックアップ を表示
• Problem 553 へ行く。
  • 1 (2024-01-12 (金) 11:17:08)

• 追加された行はこの色です。
• 削除された行はこの色です。

#author("2024-01-12T02:17:08+00:00","","")
#author("2024-01-12T02:17:40+00:00","","")
*[[Problem 553:http://projecteuler.net/problem=553]] 「べき集合のべき集合」 [#sfa14e9b]

P(n) を n 以下の正整数の集合 {1,2,...,n} とする。&br;
Q(n) を P(n) の空でない部分集合全体からなる集合とする。&br;
R(n) を Q(n) の空でない部分集合全体からなる集合とする。

元 X ∈ R(n) は Q(n) の空でない部分集合なので、それ自体が集合である。&br;
X から次のようにしてグラフを作る。

- 各 Y ∈ X は、Y をラベルとする頂点に対応する
- 2つの頂点 &tex{Y_{1}};, &tex{Y_{2}}; の間には &tex{Y_{1}}; ∩ &tex{Y_{2}}; ≠ ∅ のとき辺がある

例えば X = {{1},{1,2,3},{3},{5,6},{6,7}} から作られるグラフは図のようになる。


#img(https://projecteuler.net/resources/images/0553-power-sets.gif, c)

このグラフは2つの''連結成分''を持つ。

C(n,k) を、R(n) の元のうちグラフがちょうど k 個の連結成分を持つようなものの個数と定める。&br;
C(2,1)=6, C(3,1)=111, C(4,2)=486, C(100,10) mod 1 000 000 007 = 728209718 である。

C(&tex{10^{4}};,10) mod 1 000 000 007 を求めよ。