- 面白い問題おしえて〜な 二十四問目 [無断転載禁止]©2ch.net
189 ：１３２人目の素数さん[sage]：2017/10/09(月) 08:31:44.21 ID:TpfOSZ45 - >>187
A(n,k)の文字列において、B,CをXに置き換えた文字列をA~(n,k)とし、これを考える
これは、先頭がAかXか、最後がAかXかにより、四つに分類できる
AA型(n≧3,k≧2)
k個のAとk-1個のXが交互に並ぶ文字列 AXAX...XA のXのあるところに、n-(2k-1)個のXを挿入すると、A~(n,k)になる
これは、H[k-1,n-2k+1]=C[n-k-1,k-2] 通りあり、k-1カ所ある各Xの先頭をAかBに戻すとA(n,k)に戻るので、
2^(k-1)*C[n-k-1,k-2]
XA型およびAX型(n≧2,k≧1)
k個のAとk個のXが交互に並ぶ文字列 のXのあるところに、n-2k個のXを挿入すると、A~(n,k)になる
これは、H[k,n-2k]=C[n-k-1,k-1] 通りあり、kカ所ある各Xの先頭をAかBに戻すとA(n,k)に戻るので、
2^k*C[n-k-1,k-1]
XX型(n≧1,k≧0)
k個のAとk+1個のXが交互に並ぶ文字列 のXのあるところに、n-2k-1個のXを挿入すると、A~(n,k)になる
これは、H[k+1,n-2k-1]=C[n-k-1,k] 通りあり、k+1カ所ある各Xの先頭をAかBに戻すとA(n,k)に戻るので、
2^(k+1)*C[n-k-1,k]
これら四つの合計がA(n,k)で、2^(k-1) {1+ 4(n-k)(n-2k+1)/(k(k-1))} C[n-k-1,k-2] 通り？
|
|