|
小学名探偵 |
|
A001205からの情報ですが、
数字の種類がｎ個のとき、場合の数をA(n) と書くと、次の漸化式が成り立つようです。 A(n+1)=C(n,1)*A(n)+C(n,2)*A(n-2) 式(1) たとえば、 A(6)=C(5,1)*A(5)+C(5,2)*A(3) =5*12+10*1=70 式(2) いま、５つのノードがどれも２つの枝をもつグラフの集合をG(5)と書きます。 式(2)が成立する訳は、 新しいノードを付加する： G(5)に属する各グラフ（５つのノードがどれも２つの枝をもつ各パターン） について、５つある枝のなかから１つを選び、 その枝の上に６番目のノードを置きます。これにより、G(6)に属するグラフができます。 これによる場合の数は5*A(5)通り。 ３角形の分離： G(5)に属する各グラフ（５つのノードがどれも２つの枝をもつ各パターン） について、２つのノードを選び、この２つのノードに６番目のノードを加えた ３ノード間で閉ループ（三角形）をつくります（G(3)に属するグラフ)。 この三角形分離のために、G(5)に属するグラフから、 ２ノードがなくなってグラフはG(5-2)に属することになります。 グラフ全体は、G(3)に属するグラフとG(5-2)に属するグラフをあわせたものなので、 G(6)に属するグラフになります。 これによる場合の数はC(5,2)*A(3)通り。 合計すると、式(2)になります。 同様の議論で、式(1)が成り立ちます。 |
|
3月11日（金） 9:08:23
24685 |