結論

答えは \(\displaystyle\sum _ {i=0} ^ {N-1} \binom{2i-K}{i}\begin{bmatrix}N-1 \cr 2i-K\end{bmatrix}\) です(\(\begin{bmatrix}\bullet\end{bmatrix}\) は第一種スターリング数)。

なお、\(\displaystyle \binom{n}{m}\) や \(\begin{bmatrix}n\cr m\end{bmatrix}\) は \(0\leq m\leq n\) でない場合 \(0\) とします。

概要

\(i=0,1,\ldots,N-1\) に対して \(L(P) - 1 = i\) かつ \(R(P) - 1 = i - K\) なる \((1,2,\ldots,N)\) の順列 \(P\) を数えて和を取ります。

このような \(P\) の集合は、\(L(Q) = 2i - K\) なる \((1,2,\ldots,N-1)\) の順列 \(Q\) の集合と \(\displaystyle\binom{2i-K}{i}\) 対 \(1\) で対応させられます (※1)。\(L(P)=m\) なる \((1,2,\ldots,n)\) の順列 \(P\) は \(\begin{bmatrix}n\cr m\end{bmatrix}\) 通りである (※2) ことと併せて上記の答えが得られます。

※1について

\(L(Q)=2i-K\) なる \((1,2,\ldots,N-1)\) の順列 \(Q\) を任意に取ります。\(Q\) を prefix max が更新される項の直前で区切っていくつかのブロックに分けます (雑な物言いですが、例えば \((1,5,6,2,3,8,7,4,10,9)\) に対して \(([1], [5], [6,2,3],[8,7,4],[10,9])\) と分けるような操作を考えています)。このブロック数は \(L(Q)=2i-K\) 個です。

これらのブロックのうち \(i\) 個を赤色で、\(i-K\) 個を青色で塗ります。そして、赤色のブロックだけを元の順序を保って連結した列を \(A\), 青色のブロックだけを元の順序を保って連結して reverse した列を \(B\) とします。例えば、\(({\color{red}[1]}, {\color{blue}[5]},{\color{blue}[6,2,3]},{\color{red}[8,7,4]},{\color{red}[10,9]})\) と塗った場合は \(A=({\color{red}[1]}, {\color{red}[8,7,4]},{\color{red}[10,9]})\) で \(B=({\color{blue}[3,2,6]}, {\color{blue}[5]})\) です。\(A\) と \(B\) を \(N\) を挟んで連結することで、\(L(P)-1=i\) かつ \(R(P)-1=i-K\) なる \((1,2,\ldots,N)\) の順列 \(P\) が得られます。先ほどの例では \(P=({\color{red}[1]}, {\color{red}[8,7,4]}, {\color{red}[10,9]},[11],{\color{blue}[3,2,6]},{\color{blue}[5]})\) です。

\(Q\) から \(P\) への変換の方法は、色の塗り方だけ存在して \(\displaystyle\binom{2i-K}{i}\) 通りあります。一方で \(P\) から \(Q\) の逆変換は一意に可能です。

※2について

\(L(P)=m\) なる \((1,2,\ldots,n)\) の順列 \(P\) の集合と、\(m\) 個のサイクルに分解される \((1,2,\ldots,n)\) の順列 \(Q\) の集合を一対一対応させます。

\(m\) 個のサイクルに分解される \((1,2,\ldots,n)\) の順列 \(Q\) を任意に取ります。\(Q\) のサイクルをそれぞれ最大値が先頭になるように切り開き、最大値が小さい順に並べて連結して \(P\) を作ります。この \(P\) が \(L(P)=m\) を満たすこと、および逆変換が一意に定まることを確認できます。