解説の行間がデカすぎる!
以下、解説ページを読んだものとします。行間を埋めます。
必要十分条件の証明について
操作が可逆であることに注意します。解説によれば、操作によって文字列 と が互いに移り変われることと、次の2つが満たされることは同値です。
- 文字
A
、B
、C
のどれについても が含む個数と が含む個数が等しいこと - と のどちらに対しても操作が行えること
このうち、1番は明らかです。1番を満たすような文字列だけを考えたとき、2番が満たされれば文字列 と が互いに移り変われることを、 についての数学的帰納法を用いて証明します。
の場合は明らかです。 のときに正しいとします。
なる と を考えます。 より、文字列中には3種類のうちいずれかの文字が2文字以上存在することがわかります。対称性より、そのような文字の1つを文字A
とします。
操作を繰り返すことで、あるインデックスであって と のどちらでもその位置の文字がA
であるようなインデックスを作り、同時に削除することで文字列長を1減らすのを目標にします。もちろん、残った文字列に対しても変わらず操作が行える必要があります。
さて、まず文字列 を考えます。 に対して操作を行えるのですから、 の部分列としてABC
、BCA
、CAB
のいずれかが存在します。その部分列を対象として何回か操作することで、部分列としてABC
が存在するようにできます。
文字の位置関係のみが重要なので、今見ている部分列以外のB
とC
のことをいったん忘れることにします。すると、 は次のようになります。A
の個数は適当です。
AAAAABAAAAAAACAAAAA
B
の左にあるA
のうち、最も右にあるものを選びます。 は部分列として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
文字列 に対しても同様の操作をします。
さて、 と を同時に左から見て行って、初めて文字A
が出現する場所 を調べます。対称性から、先に にA
が出現したと考えてよいです。 を削除しても、さらに右に部分列ABC
が存在するため、変わらず操作できます。
に対して適当に操作することで、 に文字A
を持ってくることができ、さらに を削除しても変わらず操作できる、ということが示せます。現在の で場合分けします。
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
が存在するので、操作できます。
以上で の場合が の場合に帰着でき、帰納法の仮定より でも主張が正しいことが示せました。
余事象の数え上げ
1つ目の条件を満たすが2つ目の条件を満たさないものは 通りです。これについても詳しく見ておきます。
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
のみが適するということがわかりました。これらの形の文字列が何通り存在するかについては、両端の文字をどちらにいくつ割り振るかを考えることで求められます。具体的に、 に含まれる文字A
の個数を のように置くと、それぞれ 、、 通りになります。ただし、ACB
、BAC
、CBA
については2回ずつ数えられているので、 だけ引く必要があります。
よって 通りになるとわかりました。