解説の行間がデカすぎる！

以下、解説ページを読んだものとします。行間を埋めます。

必要十分条件の証明について

操作が可逆であることに注意します。解説によれば、操作によって文字列 $S$ と $T$ が互いに移り変われることと、次の2つが満たされることは同値です。

文字A、B、Cのどれについても $S$ が含む個数と $T$ が含む個数が等しいこと
$S$ と $T$ のどちらに対しても操作が行えること

このうち、1番は明らかです。1番を満たすような文字列だけを考えたとき、2番が満たされれば文字列 $S$ と $T$ が互いに移り変われることを、 $|S|\;(=|T|)$ についての数学的帰納法を用いて証明します。

$|S|=|T|=3$ の場合は明らかです。 $|S|=|T|=k\;(\ge 3)$ のときに正しいとします。

$|S|=|T|=k+1$ なる $S$ と $T$ を考えます。 $k+1 \ge 4$ より、文字列中には3種類のうちいずれかの文字が2文字以上存在することがわかります。対称性より、そのような文字の1つを文字Aとします。

操作を繰り返すことで、あるインデックスであって $S$ と $T$ のどちらでもその位置の文字がAであるようなインデックスを作り、同時に削除することで文字列長を1減らすのを目標にします。もちろん、残った文字列に対しても変わらず操作が行える必要があります。

さて、まず文字列 $S$ を考えます。 $S$ に対して操作を行えるのですから、 $S$ の部分列としてABC、BCA、CABのいずれかが存在します。その部分列を対象として何回か操作することで、部分列としてABCが存在するようにできます。

文字の位置関係のみが重要なので、今見ている部分列以外のBとCのことをいったん忘れることにします。すると、 $S$ は次のようになります。Aの個数は適当です。

AAAAABAAAAAAACAAAAA

Bの左にあるAのうち、最も右にあるものを選びます。 $S$ は部分列としてABCを含むので、そのようなAは必ず存在します。選んだAと、残したB、Cに対して1回操作します。

AAAABCAAAAAAAAAAAAA

Aについての条件から、操作後のBとCの間にはAは存在しません。

Cの右にはいくつかAが存在します。そのようなAのうち最も左にあるものを選び、BCと組み合わせて2回操作し、BCA→ABCとします。すると、BとCの間にAが存在しないような状態を保ちながらCの右にあるAを1個ずつ減らすことができます。最終的に次のような状態になります。

AAAAAAAAAAAAAAAAABC

文字列 $T$ に対しても同様の操作をします。

さて、 $S$ と $T$ を同時に左から見て行って、初めて文字Aが出現する場所 $i$ を調べます。対称性から、先に $S$ にAが出現したと考えてよいです。 $S_i$ を削除しても、さらに右に部分列ABCが存在するため、変わらず操作できます。

$T$ に対して適当に操作することで、 $T_i$ に文字Aを持ってくることができ、さらに $T_i$ を削除しても変わらず操作できる、ということが示せます。現在の $T_i$ で場合分けします。

Aの場合

そのままでよいです。さらに右にABCという部分列があるため、削除後も操作できます。

Bの場合

さらに右にAABCという部分列があります。組み合わせてBAABCとなります。次のように操作します。

BAABC
BABCA
BABCA
CABAB
CABAB
ABCAB

Aを持ってくることができました。また、Aの削除後もCABが存在するので、操作できます。

Cの場合

上と同様に組み合わせてCAABCとなります。

CAABC
CABCA
CABCA
CACAB
CACAB
AACBC

Aを持ってくることができました。また、Aの削除後もACBが存在するので、操作できます。

以上で $|S|=|T|=k+1$ の場合が $|S|=|T|=k$ の場合に帰着でき、帰納法の仮定より $|S|=|T|=k+1$ でも主張が正しいことが示せました。

余事象の数え上げ

1つ目の条件を満たすが2つ目の条件を満たさないものは $|S|$ 通りです。これについても詳しく見ておきます。

AとBを並べた状態で、Cを新たに置くことを考えます。このとき部分列としてABC、BCA、CABのいずれかを含んではいけません。そのような置き方はどのようなものであるか、観察します。連続する同じ文字を1つにまとめることで、Cを置く前の文字列についてはABABAB...またはBABABA...の形のもののみを考えればよいです。

ABの場合

CAB
ACB
ABC

この場合ACBとするしかありません。つまり、すべてのCをAとBの間に置くことになります。

ABAの場合

CABA
ACBA
ABCA
ABAC

ACBAしか適しません。

ABABの場合

CABAB
ACBAB
ABCAB
ABACB
ABABC

すべて不適です。よってABABA以降も不適であることがわかります。

BAの場合

CBA
BCA
BAC

CBAとBACが適します。組み合わせるとCBACとなります。

BABの場合

CBAB
BCAB
BACB
BABC

BACBのみが適します。

BABAの場合

CBABA
BCABA
BACBA
BABCA
BABAC

すべて不適です。よってBABAB以降も不適であることがわかります。

ACBはACBAの一部である、と考えると、結局ACBA、BACB、CBACのみが適するということがわかりました。これらの形の文字列が何通り存在するかについては、両端の文字をどちらにいくつ割り振るかを考えることで求められます。具体的に、 $S$ に含まれる文字Aの個数を $cnt_A$ のように置くと、それぞれ $cnt_A+1$ 、 $cnt_B+1$ 、 $cnt_C+1$ 通りになります。ただし、ACB、BAC、CBAについては2回ずつ数えられているので、 $3$ だけ引く必要があります。

よって $(cnt_A+1)+(cnt_B+1)+(cnt_C+1)-3=cnt_A+cnt_B+cnt_C=|S|$ 通りになるとわかりました。