\(i\) 行 \(j\) 列のマスを \((i,j)\) と書くことにします。

\(N=1\) のとき、\((1,j)\) に書かれた整数は \(B_j\) です。よって、列 \(B\) が定まれば、\(A_1\) の値は自動的に定まります。すなわち、求める場合の数は \(K^M\) です。

\(M=1\) のとき、同様の議論により、求める場合の数は \(K^N\) です。

さて、\(N,M\geq 2\) としましょう。\(A_i\) たちの最大値が \(A_1\) であり、\(B_j\) たちの最小値が \(B_1\) であると仮定して一般性を失いません。このとき、\((1,1)\) に書かれた整数は \(A_1\) 以上 \(B_1\) 以下である必要があるため、\(A_1\leq B_1\) が必要です。

逆に、\(A_1\leq B_1\) なら、条件を満たす整数の書き込み方が存在することが証明できます。実際、

• \((1,1)\) に \(A_1\) を, \((2,2)\) に \(A_2\) を, \((2,1)\) に \(B_1\) を, \((1,2)\) に \(B_2\) を、
• \((3,1),\dots, (N,1)\) に \(A_3,\dots, A_N\) を、
• \((1,3),\dots, (1,M)\) に \(B_3,\dots, A_M\) を、
• 残りのマスには、それが \(i\) 行目にあるとして \(A_i\) を

それぞれ書き込めば、条件を満たします。\(A_i\) たちの最大値 \(x\) を固定して考えれば、このような列対の個数は \(\sum_{x=1}^{K} (x^N-(x-1)^N)(K-x+1)^M\) であることが分かります。