2n人での場合の数をa[n]とおきます. おそらくですが次の漸化式が成立するという意味です: a[n]=Σ[i=0,n-1]a[i]a[n-i-1] (n≧1)(ただし a[0]=1とする)
この漸化式は以下のような考え方で得られます: 反時計回りに子どもたちに番号をつけます(1,2,..,2n) 1と糸が繋がる可能性があるのは偶奇を考えると 2,4,..,2n の n通りあります. iを1以上n以下の任意の整数とします. 2i番目の人と繋がったとすると 領域が2つに分割されます 片方は a[i]通りのつなげ方があり もう片方はa[n-i-1]通り よって このケースでのつなげ方は合計a[i]a[n-i-1]通り iを1からnまで動かして足し合わせ上記の漸化式が得られます.
ちなみにこの漸化式は解くことができて (たとえば母関数の方法というジェネリックな方法が通用する) そうすると a[n] = (2n)!/(n!(n+1)!) (いわゆるカタラン数)
125x103x78x129.ap125.ftth.ucom.ne.jp (125.103.78.129)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/70.0.3538.102 Safari/537.36 Edge/18.18363
|
|