黒いボールを置くことを「\(x\) 軸方向に \(1\) 進む」、白いボールを置くことを「\(y\) 軸方向に \(1\) 進む」と言い換えると、黒いボール \(M\) 個、白いボール \(N\) 個を並べ替える方法は、\((0, 0)\) から \((M, N)\) への経路に対応します。

\(w_i \leq b_i + K\) という条件はどのように言い換えればよいでしょうか。経路が点 \((x, y)\) を通ることは、並べ替えにおいて左から \((x + y)\) 個のボールのうち、黒いものが \(x\) 個、白いものが \(y\) 個であることと同値です。よって、この条件は「経路が \(y \leq x + K\) で表される領域に含まれる」と言い換えることができます。

\(N = 5, M = 6, K = 2\) において、 bwwwbbwbbbw という並べ方に対応する経路は以下のようになります。

明らかに、\(N > M + K\) のとき答えは \(0\) です。以下では \(N \leq M + K\) を仮定します。

\(y \leq x + K\) という条件がなければ、経路の総数は \(\binom{N + M}{N}\) です。これらのうち、条件を満たさない経路の総数を除くことを考えます。

条件を満たさない経路は、必ず直線 \(y = x + K + 1\) と共有点を持ちます。共有点のうち、\(x\) 座標が最も小さいものに注目し、原点からこの点までの経路を直線 \(y = x + K + 1\) に関して折り返してみましょう。すると、\((-K-1, K + 1)\) から\((M, N)\) ヘの経路が一つ得られます。逆に、\((-K-1, K + 1)\) から\((M, N)\) への経路は、始点は直線 \(y = x + K + 1\) の上側にあり、終点は下側にあることからこの直線と共有点をもつため、同様に折り返すと、\((0, 0)\) から \((M, N)\) への経路であって、領域 \(y > x + K\) と共通部分を持つものが一つ得られます。

以上から、条件を満たさない経路は \((-K-1, K + 1)\) から\((M, N)\) ヘの経路と一対一に対応し、その総数は \(\binom{N + M}{M + K + 1}\) となります (ただし、\(n < r\) のとき \(\binom{n}{r} = 0\) とする) 。

\(N \leq M + K\) かどうかのどうかの場合分け忘れに注意してください。

実装例 (C++)