#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 を求めよ。 IP:207.65.235.4 TIME:"2024-01-12 (金) 11:17:40" REFERER:"https://odz.sakura.ne.jp/projecteuler/?cmd=edit&page=Problem+553" USER_AGENT:"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/120.0.0.0 Safari/537.36"