19/07/28 04:04:47.20 7okwRhGQ.net
>>531
A、B、Cがそれぞれn個、自由に並べ替えてできる長さ3nの文字列に対し、
操作1「Cを取り除く」、操作２「連続するAを一つのAに、連続するBを一つのBに変換」を順に行うと、
長さ3nの文字列は、AB,ABA,ABAB,...,(AB)^n および、AとBを入れ替えた物
のいずれかに変化する。長さ3nの文字列を、この操作後の形で分類して、>>531の条件に合う物の数える。
例えば、ABABA に落ち着く物は、まずは、ACBCACBCAと復元し、
n-3個のAを三カ所のいずれかのAの下に分配し、n-2個のBを二カ所のいずれかのBの下に分配し、
n-4個のCを、2n+1カ所のいずれかに挿入or横付けすればよい。
従って、ABABA型に落ち着く文字列の数は、C[n-1,2]*C[n-1,1]*C[3n-4,2n] 個ある。
これを可能なすべての型について、和を取ればよい。
(AB)^k型 C[n-1,k-1]*C[n-1,k-1]*C[3n-2k+1,2n]
A(BA)^k型 C[n-1,k]*C[n-1,k-1]*C[3n-2k,2n]
Σ[k=1,(n+1)/2] {2*