k の左にある個数と右にある個数しか見なくてよいので、dp[i][j]=(目標の要素の左に i 個、右に j 個ある状態から目標の要素だけ残す操作列の個数) とすると、
初期値: dp[0][0]=1
遷移:
dp[i][j] += dp[i-2][j]*(i-1)(i-2)/2
dp[i][j] += dp[i][j-2]*(j-1)(j-2)/2
dp[i][j] += dp[i-1][j-1]*((i-1)(j-1)+1)
答え: dp[k][2N-k]

x>0 のとき dp[0][x]=dp[x][0]=0 なので、dp[0][_], dp[_][0] を無視して dp[1][1]=1 から始めることにする。
dp’[i][j]:=dp[i][j]/((i-1)!(j-1)!) と定める。遷移の両辺を (i-1)!(j-1)! で割り、dp’ に言い換えると以下のようになる:
初期値: dp’[1][1]=1
遷移:
dp’[i][j] += dp’[i-2][j]/2
dp’[i][j] += dp’[i][j-2]/2
dp’[i][j] += dp’[i-1][j-1]
dp’[i][j] += dp’[i-1][j-1]/((i-1)(j-1))
答え: dp’[k][2N-k]*(k-1)!(2N-1-k)!
(i,j) をグリッド上に置き、i が増える方向を「下」、j が増える方向を「右」と呼ぶ。遷移を上から順に a,b,c,d と呼ぶ。
ある点から「遷移 a,b,c のいずれかを選んで行う」ことは、
「以下の 2 つのうち 1 つを選ぶことを 2 連続で行う:
下に 1 進み、1/√2 倍する。
右に 1 進み、1/√2 倍する。
」
と同等になるので、この 2 つと遷移 d を行えると言い換える。ただし、これら 2 つを連続で行わせるため、遷移 d は i+j が偶数のときしか行えないとする。DP の遷移は以下のようになる。
dp’[i][j] += dp’[i-1][j]/√2
dp’[i][j] += dp’[i][j-1]/√2
dp’[i][j] += dp’[i-1][j-1]/((i-1)(j-1)) (i+j は偶数)