Knuth Equivalence をそのまま問う問題です．

例えば この論文 の Theorem 2.4 を読むとわかります．

これだけだとあまりにひどいので一応何をするかくらいは書いておきます．

Schensted algorithm によって，順列 \(P\) から \(2\) つの tableau \(S_P,T_P\) を作ります． 同様に \(Q\) から \(S_Q,T_Q\) を作ります．

\(S_P=S_Q\) であることが \(P\) を \(Q\) に変換可能である必要十分条件です． 一度の swap によって \(S\) が変化しないことが（場合分けとかをちゃんとやれば）確認できるため，必要性がまずわかります． 以下，\(P\) を \(Q\) に変換する手順を実際に構築することで，十分性も示します．

\(S_P\) を下の行から読むことで得られる数列を \(U\) として，\(U\) を \(P\) に変換することを目指します． 操作を逆順にすることで \(P\) を \(U\) に変換する手順も同時に得られます． \(Q\) についても同様に手順を求めることで，\(P \to U \to Q\) という手順を得ることができます．

例: \(P=(5,3,4,7,6,1,2),U=(5,7,3,4,1,2,6)\)

S_P 
 126
 34
 57

\(X=(P_1,P_2,\cdots,P_{N-1})\) と置き，さらに \(S_X\) を下の行から読んで得られる数列を \(Y\) と置きます． \(U\) を \(Y+P_N\) (\(Y\) と \(P_N\) をこの順に並べて得られる列) に変換することを目指します．これができれば，\(X,Y\) について同じ問題を再帰的に解くだけになります．

\(Y+P_N\) を \(U\) にする手順を考えます． これは，Schensted algorithm の Insertion Step をそのまま追う形でできます．

例：\(X=(5,3,4,7,6,1),Y=(5,3,7,1,4,6)\)

S_X              Y+P_N
 146  ←(2)        5371462
 37 
 5 
 ↓ 6,2 を swap
 14(2)6           5371426
 37 
 5 
 ↓ (2) が目標の位置に来たので停止，(4) を押し出していく
 1(4)26           5371426
 37 
 5 
 ↓ 1,4 を swap
 (4)126           5374126
 37 
 5 
 ↓ (4) を次の行へ移動
 126              5374126
 37   ←(4)
 5 
 ↓ (4) が目標の位置に来たので停止，(7) を押し出していく
 126              5374126
 3(7)4
 5 
 ↓ 3,7 を swap
 126              5734126
 (7)34
 5 
 ↓ (7) を次の行へ移動
 126              5734126
 34
 5    ←(7)
 ↓ (7) が目標の位置に来たので停止，終了
 126              5734126
 34
 57

すべての swap が条件を満たしていることは頑張ると確認できます． よって，\(N-1\) 回以下の操作で \(U\) を \(Y+P_N\) にすることができます． これを繰り返すことで，高々 \(N(N-1)/2\) 回の操作で \(U\) を \(P\) に変化させることができます．

よって全体で \(N(N-1)\) 回の操作で \(P\) を \(Q\) に変化させることができました．

解答例