目次
総和がSになる数列の個数
整数 $a+b+c+...=S$ を満たすような $(a,b,c,...)$ の組の個数の数え上げ方。
$S$ 個のボールを箱に入れる問題とも関連が深い。
順番を区別
$S=6$ のとき、$(2,1,3)$ と $(3,2,1)$ などは別々に数える場合。
ボールと箱の問題に置き換えたときの、箱を区別する場合。 基本的にこちらの方が数えやすい。
後述の順番を区別しない場合の「分割」と区別して、「順序付き分割」や「結合（Composition）」などという場合もある。
項数に制約無し
$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個ずつ減らすことをイメージする。
最大値が $k$
最大値が固定されている場合の順序付き分割の数。
直接は求めづらいので、「最大値が $k$ 以下」「$k-1$ 以下」の場合をそれぞれ求め、差分を取れば $k$ ちょうどのものの個数が分かる。
包除原理で求める
以下の $f$ に対し包除原理を適用し「$k+1$ 以上の要素を含まないもの」＝「最大値が $k$ 以下のもの」の個数を数える。
- $f(m):=k+1$ 以上の要素を少なくとも $m$ 個含む組成の数
まず $f(m)$ の求め方を考える。$S-1$ 個の区切り候補から選ぶという考え方をベースとする。
「$k+1$ 以上の要素が始まる区切り」を決める、という発想をする。
S=10 k=3
○ ○ ● ○ ○ ○ ○ ○ ○ ○
↑ ↑ × × × ↑ ↑ ↑ ↑
│
この区切りを「k+1以上の要素の始まり」として選んだ場合、
そこから k 個（×のところ）には区切りを入れられない
$m$ 個含む場合、$S-1-mk$ 個の区切り候補から $m$ 個を「$k+1$ 以上の要素の始まり」として選んだ上で、残りの区切りの選び方は自由となる。
- $\binom{S-1-mk}{m} \times 2^{S-1-m(k+1)}$
ただし、これには先頭要素が始まりとなる場合が含まれていないので、その場合を別途考慮する。
● ○ ○ ○ ○ ○ ○ ○ ○ ○ ↑ × × × ↑ ↑ ↑ ↑ ↑ ↑ │ ここが1つめの区切りとなるケースは、上記で考慮されていない
- $\binom{S-1-mk}{m-1} \times 2^{S-m(k+1)}$
これらの和が $f(m)$ となる。
包除原理により $\displaystyle \sum_{m=0}^{\infty} (-1)^m f(m)$ が求めたいものとなる。
Σの上側を $\infty$ と書いたが、実際には $m$ が大きくなると二項係数の $S-1-mk$ 等が負となり、$f(m)=0$ となる。 実質的に $m \le \lfloor \frac{S}{k} \rfloor$ の範囲しか考慮しなくてよいので、計算量は（階乗などの事前計算を除き） $O(\frac{S}{k})$ となる。
形式的冪級数で求める
順番を区別しない
$S=6$ のとき、$(2,1,3)$ と $(3,2,1)$ などは1つと数える場合。
ボールと箱の問題に置き換えたときの、箱を区別しない場合。
$S=6$ に対する $(2,1,3)$ などを「$S$ の分割」、英語では partition と呼ぶ。 分割の個数を「分割数（number of partitions）」と呼ぶ。
項数に制約無し
$S$ を正整数に分割する。
$S$ に対して分割数を端的に計算できる公式はない。
最大でも項数は $S$ なので、下記の「項数は $k$」の場合の $k=1～S$ を足し合わせたものが分割数となる。計算量は $O(N^2)$
ただし、工夫することで、$O(N \sqrt{N})$ でできる方法もある。
項数は $k$
DPで求める
- $\mathrm{DP}[n,k]:=n$ を $k$ 項に分割する場合の数
$\mathrm{DP}[0,0]=1$ であり、以下で再帰的に $O(Sk)$ で求められる。
- $\mathrm{DP}[S,k]=\mathrm{DP}[S-1,k-1]+\mathrm{DP}[S-k,k]$
これは、以下を意味する。
- $1$ を含むような分割
- （例）$S=6,k=3$ に対する $\{1,1,4\},\{1,2,3\}$ など
- 1を1つ取り除いた分割 $\mathrm{DP}[S-1,k-1]$ と1対1対応する。（$\{1,4\},\{2,3\}$ など）
- $1$ を含まないような分割
- （例）$S=6,k=3$ に対する $\{2,2,2\}$ など
- 全ての項から1を減らした分割 $\mathrm{DP}[S-k,k]$ と1対1対応する。（$\{1,1,1\}$ など）
または、以下の更新方法でもよい。計算量は変わらず $O(Sk)$
- $\displaystyle \mathrm{DP}[S,k]=\sum_{i=1}^{k}\mathrm{DP}[S-k,i]$
項数 $i$ の分割に対し、$k-i$ 個の $0$ を追加して項数を $k$ にした上で、各要素を1ずつ増やす、と考える。
母関数から求める
-
- p.32～
$k$ が小さい（$～100$ 程度）一方、$S$ が巨大（$10^{18}$ 程度）で、DPでは求められない場合に有効。
形式的冪級数の初等知識が必要となる。
また、後述の「最大値が $k$」で示すように、「項数が $k$ の分割と、最大値が $k$ の分割の個数は一致する」ということを利用する。
$k$ を固定した時、「和が $i$ となるような、最大値が $k$ 以下となる分割の仕方」を $a_i$ とする。
これが求められたら、$a_S-a_{S-1}$ が「最大値が $S$ の分割の個数」＝「項数が $S$ の分割の個数」として求められる。
$a_i$ は、以下の式の $x^i$ の係数として求められる。
- $f(x)=(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...(1+x^k+x^{2k}+...)$
さらに、これは以下のように変形できる。
- $\displaystyle f(x)=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3}...\frac{1}{1-x^k}$
分母を畳み込みによって小さい方からマージしていくと、$O(k^2 \log{k})$ 程度で全てマージでき、次数は $\frac{k(k+1)}{2}$ となる。
さらに、$\frac{P(x)}{Q(x)}$ のような多項式で表される数列の第 $S$ 項は、 多項式の次数を $d$ として、Bostan-Moriにより $O(d \log{d} \log{S})$ で求められる。
よって、全体 $O(k^2 \log{k} \log{S})$ で求められる。
最大値が $k$
以下の2つは一致する。
- 項数は $k$ 項、各項が取れる値は任意の自然数（前項の内容）
- 項数は任意、分割中に現れる最大値はちょうど $k$（本項の内容）
分割の仕方をブロックの積み上げで表現したとき、縦に見るか横に見るかの違いだけとなる。この表し方は「ヤング図形」という。
S = 13
k=4項に分割 最大値がk=4になるように分割
2 □□ □□
3 □□□ □□□
3 □□□ □□□
5 □□□□□ □□□□□
4 4 3 1 1
項数が $k$、最大値が $m$
以下に記載がある。
大小関係の構成による場合分け
$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$ が小さいときに限るが、このようにすれば任意の大小関係での分割数を求められる。