No.895
\(n = a + b + c\) とする. ビットは下から \(1\) ビット目, \(2\) ビット目と数え, \(x, y, z\) の最上位ビットを \(x_r, y_r, z_r\) とする.
まず, \(x_r = n\) は決定である.
次に \(z_r = i \ (c \leq z_r \leq n-2)\) を固定し, \(z = z_j\) と決まったときの \(x, y\) の組み合わせの数を考える.
これは残りの \(n - 1 - c\) ビットのうち \(y\) に使う \(b\) ビットの組み合わせの数 \(\combi{n-1-c}{b}\) から \(b \lt c\) となる数, すなわち \(b\) ビットがすべて \(i\) 以下に収まる数 \(\combi{i-c}{b}\) を引いたものである.
これを \(z_j\) すべてについて行った和は, \(z_j\) の \(i\) ビット目は \(\combi{i-1}{c-1}\) 回登場し, \(k\) ビット目 \((k \lt i)\) は \(\combi{i-2}{b-2}\) 回登場するので,
\[(\combi{n-1-c}{b} - \combi{i-c}{b}) \times (\combi{i-1}{c-1} 2^{i-1} + \combi{i-2}{c-2} (2^{i-1} - 1))\]となる. これをすべての \(i\) について計算する.