18/08/09 01:13:36.39 w0c/gBS2.net
>>773
条件を満たす長さnの順列の数をa[n]とおく。
a[2] = 0,
a[3] = 2 (ABA，ACA)
a[4] = 2 (ABCA，ACBA)
a[5] = 6 (ABABA，ABACA，ABCBA，ACABA，ACACA，ACBCA)
漸化式 >>774 より
a[n] + a[n-1] = 2(a[n-1] + a[n-2]) = … = 2^(n-3)･(a[3] + a[2]) = 2^(n-2),
a[n] -2a[n-1] = -(a[n-1] -2a[n-2) = … = (-1)^(n-3)･(a[3] -2a[2]) = -2(-1)^(n-2),
これより
a[n] = (2/3) {2^(n-2) - (-1)^(n-2)},