二項係数の積の総和と怪文書

なんかこの前のARCで出てえらい目みたので思いつきでまとめていきたいとおもいます。
verifyとかしてないし議論の正確性は保証しません。

二項係数の積の総和をまとめることを組み合わせ論的解釈を通して試みていきたいと思います。
ここでは、 $(x_i < y_i)$ ならば

$\binom{x_i}{y_i}= 0$

とします。

1. 下が不定

Q.
非負整数列 $a_1, a_2, ..., a_n$ と非負整数 $S$ が与えられます。
総和が $S$ になるようなあり得る全ての非負整数列 $x_1, x_2, ..., x_n$ について、 $\prod_{i=1}^{n}{\binom{a_i}{x_i}}$ を計算して総和を出力してください。

ごちゃごちゃと数式で書けば下式のような感じ。ウワsumの下にsumがあるきも

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{a_i}{x_i}}$

言い方を変えていきたいと思います。

Q.
$n$ 個の箱があり、 $i$ 番目の箱には $a_i$ 個の区別可能なボールが入っています。各箱からいくつかボールを選んで合計 $S$ 個ボールを取り出すとき、取り出し方は何通りありますか。
（ただし、取り出し方が同じであるというのは取り出した後のボールの集合が一致することを指します。）

うんうん。例えば次のような感じです。

ex.)
a = [5, 2, 2], S = 5

ooxox xx ox

上の||で囲まれたところが箱で、内部のoが残ったボール、xが取り出したボールを指しています。
この場合は1番目の箱から2個、2番目から2個、3番目から1個取り出す例のひとつを表しています。

ん？

ooxox

↓

ooxox xx ox

↓

ooxoxxxox

なんということでしょう。箱を破壊してボールをひとつにまとめることができてしまいました。なにこれ？
重要なのは「ボールの区別ができる」ということが「箱の区別」を包含しているということです。

取り出したボールが区別可能なら、例えば取り出した後のボールを見て「あ、この形は2番目の箱から取り出した左から1番目のボールだな......」と解釈して箱の状態を復元することができるはずです。
この理屈でいけば、二項係数の積の総和をひとつの大きな二項係数に置き換えられそうです。

問題がさらに言い換えられます。

Q.
$1$ 個の箱があり、箱には $\sum_{i=1}^{n}{a_i}$ 個の区別可能なボールが入っています。各箱から合計 $S$ 個ボールを取り出すとき、取り出し方は何通りありますか。

クソ簡単やん＾＾
というわけで、

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{a_i}{x_i}} = \binom{\sum_{i=1}^{n}{a_i}}{S}$

このように変形できました。ひゃ〜〜〜〜

2. 上が不定

Q.
非負整数列 $a_1, a_2, ..., a_n$ と非負整数 $S$ が与えられます。
総和が $S$ になるようなあり得る全ての非負整数列 $x_1, x_2, ..., x_n$ について、 $\prod_{i=1}^{n}{\binom{x_i}{a_i}}$ を計算して総和を出力してください。

少し変わりました。 $a_i$ と $x_i$ が入れ替わりましたね。下式で表せます。

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{x_i}{a_i}}$

言い方を変えていきたいと思います。

Q.
$n-1$ 個の仕切りがあり、横一列に並んだ互いに区別可能な $S$ 個のボールたちの間に仕切りを入れて $n$ 個の区間にボールを分割します。この状態でそれぞれ $i$ 番目の区間から $a_i$ 個ボールを取り出す方法は何通りありますか。
（ただし、取り出し方が同じであるというのは、仕切りの置き方が同一で、取り出した後のボールの集合も一致することを指します。）

いや、むっっっっっっっっっず

ex.)
a = [5, 2, 2], S = 12
oxxxox || oxx || xx
xxxxoo || xxo || xx

こんな例も作れるわけですが......
選んだボールxと仕切り||だけ取り出してみます

ん？
oxxxox || oxx || xx　→ xxxx||xx||xx
xxxxoo || xxo || xx　→ xxxx||xx||xx

おやおや＾＾
xと||の順序関係は決まっているので、この中での順列は考えなくて良いです。
ということはxと||は同じものとして見做して良いので、||→xとしましょう。

仕切りの数は $n-1$ 個ですから、次のように問題が言い換えられます。

Q.
横一列に $n-1+S$ 個の区別可能なボールが並んでいます。各箱から合計 $n-1+ \sum_{i=1}^{n}{a_i}$ 個ボールを取り出すとき、取り出し方は何通りありますか。

やった〜〜

したがって下式が得られました。

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{x_i}{a_i}} = \binom{n-1+S}{n-1+\sum_{i=1}^{n}{a_i}}$

3. 上下が不定

Q.
非負整数 $S, T$ が与えられます。
総和が $S$ になるようなあり得る全ての非負整数列 $x_1, x_2, ..., x_n$ と、総和が $T$ になるようなあり得る全ての非負整数列 $y_1, y_2, ..., y_n$ について、 $\prod_{i=1}^{n}{\binom{x_i}{y_i}}$ を計算して総和を出力してください。

ふむふむ。式に表すと次のような形です。

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum} \underset{\sum_{i=1}^{n}{y_i}=T}{\sum} \prod_{i=1}^{n}{\binom{x_i}{y_i}}$

これは実は2.において仕切り||と選んだボールxを区別するバージョンにあたります。
合計 $n-1+T$ 個の（仕切り||と選んだボールx）から $n-1$ 個の仕切り||の位置の組み合わせを考えると、

$\binom{n-1+T}{n-1}$

とわかるので、これを2.で得られた式の右辺に乗じれば良さそうです。

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum} \underset{\sum_{i=1}^{n}{y_i}=T}{\sum} \prod_{i=1}^{n}{\binom{x_i}{y_i}=\binom{n-1+S}{n-1+T}\binom{n-1+T}{n-1}}$

二項係数を階乗に直して少し計算してもいいでしょう

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum} \underset{\sum_{i=1}^{n}{y_i}=T}{\sum} \prod_{i=1}^{n}{\binom{x_i}{y_i}}=\frac{(n-1+S)!}{(S-T)!(n-1)!T!}$

4. まとめ