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

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

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

項数に制約無し

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

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

項数は $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)+\ldots+a(S-k,k)$

計算量はいずれも $O(S k)$

母関数から求める

$k$ を固定した時の $a(1),a(2),\ldots$ の母関数は、$\dfrac{1}{(1-x)(1-x^2)(1-x^3) \ldots (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$ が小さいときに限るが、このようにすれば任意の大小関係での分割数を求められる。

programming_algorithm/number_theory/partitions.txt · 最終更新: 2021/04/14 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0