総和がSになる数列の個数

整数 $a+b+c+...=S$ を満たすような $(a,b,c,...)$ の組の個数の数え上げ方。

$S$ 個のボールを箱に入れる問題とも言う。

• 「写像12相」を総整理！ 〜 数え上げ問題の学びの宝庫 〜 - Qiita

$S=6$ のとき、$(2,1,3)$ と $(3,2,1)$ などは別々に数える場合。

ボールと箱の問題に置き換えたときの、箱を区別する場合。

基本的にこちらの方が数えやすい。

$S$ を正整数に分割する方法: $2^{S-1}$

|------------ S -----------|
 ○  ○  ○  ○  ○  ○  ○
   ↑  ↑  ↑  ↑  ↑  ↑


 ○  ○｜○  ○  ○｜○  ○  =  (2, 3, 2)
 ○｜○  ○｜○｜○｜○  ○  =  (1, 2, 1, 1, 2)

それぞれの↑に区切りを入れるか入れないか。

$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 となる。

$S$ を正整数に分割する。

• A000041 - OEIS

最大でも項数は $S$ なので、下記の「項数は $k$」の場合の $k=1～S$ を足し合わせたものが答えとなる。

$S$ を $k$ 個の正整数に分割する。

• A008284 - OEIS

正整数でなく $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}

$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$ が小さいときに限るが、このようにすれば任意の大小関係での分割数を求められる。