出典：https://x.com/yosupot/status/1084451962060365825

元の問題の代わりに、操作列をランダムに選んだときのスコアの和の期待値を求める考えます。その期待値の \(\frac{(H+W)!}{(H+W-K)!}\) 倍が元の問題の答えになります。

確率変数 \(X_{i,k}\) を「直線 \(x=i\) が \(k\) 回目の切断までに選ばれたとき \(1\) 、選ばれなかったとき \(0\)」と定めます。同様に \(Y_{i,k}\) を定めます。

\(k\) 回目の切断でのスコアは \((1+\sum_i X_{i,k})(1+\sum_j Y_{j,k})\) であり、その期待値は期待値の線形性より

\(\displaystyle E\left[\left(1+\sum_i X_{i,k}\right)\left(1+\sum_j Y_{j,k}\right)\right] =1+\sum_i E[X_{i,k}]+\sum_j E[Y_{j,k}] + \sum_{i,j} E[X_{i,k}Y_{j,k}]\)

となります。ここで確率変数の”意味”を考えることで、任意の \(i,j,k\) で \(E[X_{i,k}]=E[Y_{j,k}]=\frac{k}{H+W}\)、\(E[X_{i,k}Y_{j,k}]=\frac{k}{H+W}\frac{k-1}{H+W-1}\) となることがわかり、

\(\displaystyle 1+\left(\sum_i E[X_{i,k}]+\sum_j E[Y_{j,k}]\right) + \sum_{i,j} E[X_{i,k}Y_{j,k}]=1+k+\frac{HWk(k-1)}{(H+W)(H+W-1)}\)

となります。操作列に対するスコアはこれの \(k\) に関する和であることから \(K+\frac{K(K+1)}{2}+\frac{HW(K+1)K(K-1)}{3(H+W)(H+W-1)}\) となります。