総和がSになる数列の個数
整数 $a+b+c+...=S$ を満たすような $(a,b,c,...)$ の組の個数の数え上げ方。
$S$ 個のボールを箱に入れる問題とも言う。
順番を区別
$S=6$ のとき、$(2,1,3)$ と $(3,2,1)$ などは別々に数える場合。
ボールと箱の問題に置き換えたときの、箱を区別する場合。
基本的にこちらの方が数えやすい。
項数に制約無し
$S$ を正整数に分割する方法: $2^{S-1}$
|------------ S -----------| ○ ○ ○ ○ ○ ○ ○ ↑ ↑ ↑ ↑ ↑ ↑ ○ ○｜○ ○ ○｜○ ○ = (2, 3, 2) ○｜○ ○｜○｜○｜○ ○ = (1, 2, 1, 1, 2)
それぞれの↑に区切りを入れるか入れないか。
項数は $k$
$S$ を $k$ 個の正整数に分割する方法: ${}_{S-1}C_{k-1}$
|------------ S -----------|
○ ○ ○ ○ ○ ○ ○
↑ ↑ ↑ ↑ ↑ ↑
$S-1$ 箇所のどこかに区切りを $k-1$ 個入れるパターンと言い換えられる。
$k$ 個の非負整数に分割する場合は、${}_{S+k-1}C_{k-1}$ となる。
$S+k$ の $k$ 個の正整数への分割方法を求めた後、$k$ 項を1個ずつ減らすことをイメージする。
順番を区別しない（組合せ数）
$S=6$ のとき、$(2,1,3)$ と $(3,2,1)$ などは1つと数える場合。
ボールと箱の問題に置き換えたときの、箱を区別しない場合。
分割数、英語では partition と呼び、その場合の数は number of partitions となる。
項数に制約無し
項数は $k$
$S$ を $k$ 個の正整数に分割する。
正整数でなく $k$ 項の非負整数に分割するなら、足りない項数をゼロ埋めすれば、$1～k$ 項の正整数に分割した場合の総和と同じことになる。
S=6
1以上 0以上（k=4）
k=1: {6} → {0,0,0,6}
k=2: {1,5},{2,4} etc. → {0,0,1,5},{0,0,2,4}
k=3: {1,1,4} etc. → {0,1,1,4}
k=4: {1,1,2,2} etc. → {1,1,2,2}
DPで求める
$a(0,0)=1$、他を $0$ で初期化する。以下で求められる。
- $a(S,k)=a(S-k,k)+a(S-1,k-1)$
- 以下の合計だと考える
- $a(S-k,k)$: 全ての項が2以上の場合、1ずつ減らした場合の数と一致
- $a(S-1,k-1)$: 1の項がある場合、それを除いた場合の数と一致
または、以下でもよい。
右辺は非負整数への分割の方法の数で、その各項に等しく1を加えた結果は $a(S,k)$ と一致する。
- $a(S,k)=a(S-k,1)+a(S-k,2)+...+a(S-k,k)$
計算量はいずれも $O(S k)$
母関数から求める
-
- p.32～
$k$ を固定した時の $a(1),a(2),...$ の母関数は、$\dfrac{1}{(1-x)(1-x^2)(1-x^3) ... (1-x^k)}$ となるらしい。
証明は上記のリンク先のpdfにあるが、難しい。
ともかく、これを計算した時の $x^S$ の係数が答えとなる。
これは、競プロ界隈では“きたまさ法”や“高速きたまさ法”と呼ばれている方法で $O(k^2 \log{S})$ や $O(k \log{k} \log{S})$ で求められる。
大小関係の構成による場合分け
$S$ の $k=6$ 個への分割で、昇順に並べたときの6項間の関係がたとえば $A \lt B = C \lt D = E = F$ になるようなものの個数を求める。
この関係性のパターンは、$k-1$ 個ある2項間がそれぞれ $\lt$ か $=$ かで $2^{k-1}$ パターン存在する。 全て調べて総和を取ると、項数が $k$ になる分割数と一致する。
同じ値が何個、何組あるかの構成が重要な場合に用いるが、 上記の通り全探索には $2^{k-1}$ かかるのであまり大きな $k$ には使えない。
$A$ から順に値を決めてDPすることで $O(Sk)$ くらいで求めることも可能だが、 ある関係性パターンに対して $O(k^6 \log{S})$ や $O(k^2 \log{k} \log{S})$ などで求める方法もある。
先頭に便宜的に0を補い差分を取ると、$S$ は以下のように表せる。
0 < A < B = C < D = E = F
* * * CD間の差分 z * 3 -,
* * * * * AB間の差分 y * 5 -| 合計がS
* * * * * * 0A間の差分 x * 6 -'
$6x+5y+3z=S$ を満たす正整数 $(x,y,z)$ の組の個数に言い換えられ、 これは順序も区別するので、より数えやすい形となる。
和が $S$ となる組の個数を $a_S$ として包除原理を使うと、以下のように表せる。
- $a_S=a_{S-6}+a_{S-5}+a_{S-3}-a_{S-6-5}-a_{S-6-3}-a_{S-5-3}+a_{S-6-5-3}$
- 1項が1小さいケース - 2項が1小さいケース + 3項が1小さいケース
- 変数が4以上の場合も、同様に足し引きする
これは、$a_S$ の14項間漸化式となる。
漸化式は行列の形で表せ、これはダブリングにより $\log{S}$ で行える。
\( \left(\begin{array}{c} a_S \\ a_{S-1} \\ a_{S-2} \\ a_{S-3} \\ \vdots \\ a_{S-13} \end{array}\right) = \left(\begin{array}{cccccccccccccc} 0 & 0 & 1 & 0 & 1 & 1 & 0 & -1 & -1 & 0 & -1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \vdots & & & & & & & \ddots & & & & & & \vdots \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right) \left(\begin{array}{c} a_{S-1} \\ a_{S-2} \\ a_{S-3} \\ a_{S-4} \\ \vdots \\ a_{S-14} \end{array}\right) = \left(\begin{array}{cccccccccccccc} 0 & 0 & 1 & \ldots & 1 \\ 1 & 0 & 0 & \ldots & 0 \\ 0 & 1 & 0 & \ldots & 0 \\ 0 & 0 & 1 & \ldots & 0 \\ \vdots & & & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & 0 \end{array}\right)^{S-14} \left(\begin{array}{c} S_{14} \\ S_{13} \\ S_{12} \\ S_{11} \\ \vdots \\ S_{1} \end{array}\right) \)
行列サイズが最大で $O(k^2)$、このダブリング計算は $O(k^6 \log{S})$ かかる。
全ての関係パターンについて計算する場合は、計算量の立式がよくわからないけど、$\log{S}$ を除いた部分の計算量が $k=10$ で $2 \times 10^7$ を超えてくる。
ここでも高速きたまさ法や、線形漸化式を満たす数列の N 項目を計算するアルゴリズム を使うと、 $k$ を固定したときの計算量が $O(k^2 \log{k} \log{S})$ に落とせ、全パターンでも $k=12$ で $10^7$ を超える程度となる。（あんまかわんないな）
$k$ が小さいときに限るが、このようにすれば任意の大小関係での分割数を求められる。
