|
小学名探偵 |
|
#24685 訂正します。
A001205からの情報ですが、 数字の種類がｎ個のとき、場合の数をA(n) と書くと、次の漸化式が成り立つようです。 A(n+1)=C(n,1)*A(n)+C(n,2)*A(n-2) 式(1) 式(1)が成立する訳は、 いま、Ｎ個のノードがどれも２つの枝をもつグラフの集合をG(n)と書きます。 G(n+1)に属するグラフにおいて、(n+1)番目のノード （G(n)に属するグラフはないノード）は、 （１）一筆書きされる４以上のノードのひとつであるか、 （２）一筆書きされる３つのノードのひとつであるか のいずれかです。 （１）については、つぎの方法で得られます。 新しいノードを付加する： G(n)に属する各グラフ（n個のノードがどれも２つの枝をもつ各パターン） について、n本ある枝のなかから１つを選び、 その枝の上に(n+1)番目のノードを置きます。 これによる場合の数はn*A(n)通り。 （２）については次に方法で得られます。 ３角形の分離： ｎ個のノードののなかから、２個のノードを選び、この２個のノードに (n+1)番目のノードを加えた３ノード間で閉ループ（三角形）をつくります。 そして、残りｎ−２個のノードでG(n-2)に属するグラフをすべてつくります。 これによる場合の数はC(n,2)*A(n-2)通り。 したがって、式(1)が成り立ちます。 |
|
3月11日（金） 12:47:12
24689 |