\(N\) と \(A-B\) の偶奇が一致する場合、答えは \(0\) である。

以下 \(N\) と \(A-B\) の偶奇が一致していない場合を考える。
また、負の要素を含む数列のスコアは \(0\) であるため、考慮する良い数列は非負整数から構成されるものに限定する。

簡単のためにまずは \(A=B=0\) の場合を考える。

実は、長さが \(N\) 、初項と末項が \(0\) であるような良い数列 \(X\) のスコアは次の問題の答えと等しい。

---

\(M = (N-1)/2\) とします。

\(M\) 個のボールと \(1\) つの袋があります。ボールには \(1 \ldots M\) と番号がついています。

あなたは \(i = 2 \ldots N\) について、 \(X_i - X_{i-1}\) の値に応じて次のいずれかの行動を取ります。

1. \(X_i - X_{i-1} = +1\)：袋に入れていないボールのうち番号が最も小さいボールを袋に入れる。ただし既に捨てたボールは選ぶことができない。
2. \(X_i - X_{i-1} = -1\)：袋に入っているボールを \(1\) つ選び、捨てる。

ボールを捨てる順番としてありえるのは何通りですか？

---

この言い換えを踏まえた上で元の問題を観察すると、(\(A=B=0\) の場合の)元の問題は次のように言い換えることができる。

---

\(M = (N-1)/2\) とします。

\(M\) 個のボールと \(1\) つの袋があります。ボールには \(1 \ldots M\) と番号がついています。

あなたはボールが全て捨てられるまで次のいずれかの行動を取ります。

1. 袋に入れていないボールのうち番号が最も小さいボールを袋に入れる。ただし既に捨てたボールは選ぶことができない。
2. 袋に入っているボールを \(1\) つ選び、捨てる。

行動の列として考えられるのは何通りですか？ボールを捨てる順番が同じであっても行動 \(1\) と行動 \(2\) のタイミングが異なる場合は別々に数え上げることに注意してください。

---

ボール \(1 \ldots (N-1)/2\) を捨てるタイミングを数え上げることで、答えは \((N-2)!!\) になる。

次に \(A=B=0\) の制限を \(A \leq B\) まで緩めて考える。 すると元の問題文は (答えの \(\frac{B!}{A!}\) 倍の違いを除いて) 次のように言い換えることができる。

---

\(M = (N+A+B-1)/2\) とします。

\(M\) 個のボールと \(1\) つの袋があります。ボールには \(1 \ldots M\) と番号がついています。

\(1 \ldots A\) の番号のボールはあらかじめ袋に入っています。

あなたは袋に入れていないボールがなくなり、かつ袋の中のボールの個数が \(B\) 個になるまで次のいずれかの行動を取ります。

1. 袋に入れていないボールのうち番号が最も小さいボールを袋に入れる。ただし既に捨てたボールは選ぶことができない。
2. 袋に入っているボールを \(1\) つ選び、捨てる。

行動の列として考えられるのは何通りですか？ボールを捨てる順番が同じであっても行動 \(1\) と行動 \(2\) のタイミングが異なる場合は別々に数え上げることに注意してください。

---

この問題は \(1 \ldots A\) の番号のボールが最後袋の中に何個残っているかで場合分けすることで解くことができ、答えの具体形は次のように書ける。

\[\sum_{i=0}^{A} \binom{A}{i}\frac{1}{(B-i)!}\binom{2M-A-B}{A+B-2i}(A+B-2i)!(2M-2A-2B+2i-1)!! \\ = \sum_{i=0}^{A}\frac{A!(2M-A-B)!(2M-2A-2B+2i-1)!!}{(A-i)!i!(B-i)!(2M-2A-2B+2i)!}\]

ただし \((-1)!! = 1, (-2)!!=0, (-3)!! = 0, (-4)!!=0, \ldots\) とする。

これより元の問題の答えは次のように書ける。

\[ \frac{B!}{A!} \sum_{i=0}^{A}\frac{A!(2M-A-B)!(2M-2A-2B+2i-1)!!}{(A-i)!i!(B-i)!(2M-2A-2B+2i)!} \\ = \sum_{i=0}^{A}\frac{B!(N-1)!(N-A-B+2i-2)!!}{(A-i)!i!(B-i)!(N-A-B+2i-1)!}\]

以上では \(A \leq B\) の条件を課していたが、\(B < A\) の場合も同様の式で答えは記述される(\(\Sigma\) の上限が \(A\) から \(B\) になる )。

---

おまけ

以下量子力学を学んだことがある方向けの補足です。

実は本問題の答えは \(\bra {A}(a+a^†)^N \ket{B} \times \sqrt{\frac{B!}{A!}}\) に等しくなります。