組合せ係数と対称性で数える

概要

組合せ係数・数え上げ

選択順・順列・分配を二項係数や階乗と対称性で式化する。

有限体部分空間のrank別計数

有限体上の部分空間をrankごとに分類し、Gaussian binomial係数などでspan条件を数え上げる。連立方程式を解く技能とは区別する。

Stirling変換と階乗基底変換

冪基底と下降階乗基底の係数をStirling数で相互変換し、rank別の計数列を目的の基底へ移す。

素数pのもとでもn≥pならn!は0になり、通常の階乗・逆階乗式は使えない。Lucasの定理はn,kのp進各桁についてC(n,k)=∏C(n_i,k_i) mod pと分解する。k_i>n_iの桁があれば0。0〜p−1の階乗を前計算し、ABC279 Exの巨大引数の係数計算へ接続する。

ABC234 Fのように文字の在庫から異なる文字列を数える場合を考える。入力: 処理済み文字種だけで作れる長さlの文字列数dp[l]と、新文字の在庫c。初期値は空文字列dp[0]=1。

変換: 新文字をk個使うなら、完成後のl+k個の位置から新文字の位置をk個選ぶ。残りの位置には元の文字列を順に入れるため、一対一対応から係数はC(l+k,k)。同じ文字同士は区別しないのでk!を掛けない。

出力: next[l+k]+=dp[l]C(l+k,k)を0≤k≤cで更新する。k=0も含め、最後は正の長さだけ足す。長さ上限まで階乗と逆階乗を用意する。

転用条件: 新しい要素が同一種類であり、元の相対順序が保存されることを確認する。ABC217 Gのラベルなし集合分割では、挿入位置でなく既存群への合流先を数える別のDPになる。

考え方

二項係数は位置集合の選択、multinomialは種類ごとの配置、Stirling数は集合の分割など、式の各因子に役割を持たせる。どの対象を区別しているかで同じ見かけの式の意味が変わる。

Gaussian二項係数を基底の重複から導く

qを素数冪とし、有限体F_q上のn次元空間のr次元部分空間数をG_q(n,r)と書く。まず、順序付きの独立なr本のベクトルを数える。i本を選んだ時点のspanにはq^i個のベクトルがあるので、次の選択肢はq^n−q^i個である。一方、同じr次元部分空間の順序付き基底は∏_{i=0}^{r−1}(q^r−q^i)通りある。したがって

G_q(n,r)=∏_{i=0}^{r−1}(q^n−q^i) / ∏_{i=0}^{r−1}(q^r−q^i)=∏_{i=1}^r(q^{n−r+i}−1)/(q^i−1)

となる。これがGaussian二項係数である。r=0の空積は1とし、r<0またはr>nなら0。F_2の3次元空間で一次元部分空間を数えると、非零ベクトル7個を各部分空間の非零ベクトル1個で割って7となる。F_3なら非零ベクトル26個を各部分空間の2個で割って13となり、ベクトル数と部分空間数の違いが見える。

rank別計数では、まずspanとなる部分空間を選び、その中で生成列を数える。固定したr次元部分空間Wをspanする順序付きm本のベクトルは、基底で座標化したr×m行列がfull row rankになる場合であり、∏_{i=0}^{r−1}(q^m−q^i)通り。よって、n次元空間のm本の生成列でrankがrのものはG_q(n,r)∏_{i=0}^{r−1}(q^m−q^i)通りである。指定ベクトルをspanに含む条件などがある場合は、それを満たす部分空間だけを選ぶよう最初の因子を変える。

有限体のサイズqと、答えを出力する法pは別の値である。上の商は整数として意味を持つが、法pで分母を逆元に置き換えるには各分母がpと互いに素でなければならない。素数pでもq^i−1≡0 mod pならこの式で除算できない。

除算を避ける計算法は次の漸化式である。

G_q(n,r)=G_q(n−1,r)+q^{n−r}G_q(n−1,r−1)

固定した(n−1)次元部分空間Hに含まれる場合が第一項。含まれない場合、Hとの交わりは(r−1)次元のWとなる。Hの外の固定ベクトルuを一つ取り、外へ出るベクトルをu+h(h∈H)の形に正規化すると、同じ部分空間を作るのはhの差がWに属するときである。したがって選択肢は|H/W|=q^{n−r}通りで、第二項になる。G_q(0,0)=1と範囲外0からDPすれば、任意の出力の法で計算できる。

Stirling数で冪と下降階乗を変換する

下降階乗をx_(k)=x(x−1)…(x−k+1)、x_(0)=1と書く。第二種Stirling数S(n,k)はn個の区別される要素をk個の空でないラベルなし群へ分ける数であり、

x^n=Σ_{k=0}^n S(n,k)x_(k)

が成り立つ。整数x≥0では、n個からx個への写像を、像の大きさkと同じ行き先の群へ分けて数えている。群を選ぶS(n,k)と、それぞれに異なる行き先を割り当てる下降階乗の積であり、同じ多項式なので一般のxにも成り立つ。

逆向きには、符号付き第一種Stirling数s(n,k)を下降階乗の冪係数として定義する。

x_(n)=Σ_{k=0}^n s(n,k)x^k

符号なし第一種Stirling数をc(n,k)と書く記法では、s(n,k)=(−1)^{n−k}c(n,k)である。たとえばx^3=x_(3)+3x_(2)+x_(1)、逆にx_(3)=x^3−3x^2+2xとなる。

入力が次数D以下の冪係数a_nで、P(x)=Σ_n a_n x^nを下降階乗基底の係数b_kへ直すなら、出力はb_k=Σ_{n=k}^D a_n S(n,k)。逆に下降階乗係数b_nから冪係数へ直すならa_k=Σ_{n=k}^D b_n s(n,k)である。変換の向きと添字をこの展開式から決める。

計数列に対するStirling変換は、同じ係数行列を別の向きで使う。t個の異なる対象へt個の群を割り当てる方法をF_tとし、m個の位置から繰り返し選ぶ列の数をG_mとすると、同じ対象を選ぶ位置が一つの群になり、G_m=Σ_{t=0}^m S(m,t)F_tとなる。逆変換はF_m=Σ_{t=0}^m s(m,t)G_t。ABC278 Exでは、この変換によって繰り返しを許す列のrank別計数から異なる要素を選ぶ列の計数へ戻す。多項式の係数変換と計数列の変換では、和を取る添字の向きが異なることに注意する。

標準的な計算はS(0,0)=s(0,0)=1、範囲外0から

S(n+1,k)=S(n,k−1)+kS(n,k)、s(n+1,k)=s(n,k−1)−n s(n,k)

で表を作る。第二種では新要素が一群を作るか既存のk群に入るかを分ける。第一種ではx_(n+1)=(x−n)x_(n)の係数を比べる。いずれも加減乗算だけであり、法上の除算を必要としない。

Lucasの桁分解を構成する

素数pでは(1+x)^p≡1+x^pだから、n=Σ_i n_i p^iに対して (1+x)^n≡∏_i(1+x^(p^i))^n_i。各因子から選べる次数は0,…,n_i<pの桁で、p進表記の一意性によりx^kの係数は∏_i C(n_i,k_i)になる。k_i>n_iの桁は選べず0。これが巨大nに対しても成立する根拠である。

0,…,p−1の階乗と逆階乗を作り、n,kをpで割って各剰余桁を取り、桁係数を掛けながら商へ進む。前計算O(p)時間・空間、query O(log_p(n+1))。p自体が巨大ならO(p)前計算は実用的でなく、必要な小係数の計算法も別に評価する。n<pのO(1)公式とLucasの全費用は同じではない。

成立条件と計算量

素数mod p、前計算上限N<pなら階乗・逆階乗をO(N)で作り二項係数O(1)。N≥pでは階乗が0になりLucasなどへ移る。重複選択、空集合、負の引数、対称性で割る根拠を確認する。

Gaussian二項係数はqの冪を前計算すれば一つの積の計算がO(r)回の法上の演算となる(逆元計算は別途必要)。q整数[i]_q=1+q+…+q^{i−1}とq階乗[i]_q!=∏_{j=1}^i[j]_qを使い、必要なq階乗が出力の法で可逆なら、上限NまでO(N)回の演算と逆元計算で前計算し、各係数をO(1)で得られる。除算を使わない漸化式はn≤N,r≤Rの範囲をO(NR)時間、行を使い回してO(R)空間で計算できる。

Stirling数の表はO(D²)時間・空間、表を用いた一つの係数列・計数列の変換はO(D²)時間。特定の一行のs(D,k)だけが必要なら、積∏_{i=0}^{D−1}(x−i)の係数を求めればよく、高速な多項式積を使う分割統治へ接続できる。ABC278 Exの大きな制約では二次時間の標準法だけでは足りず、公式解説の畳み込みによるrank別計数と第一種Stirling数の一行の計算を組み合わせる。必要なのが表全体、一行、変換後の列のどれかを先に確定する。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。通常・Gaussian二項係数、Stirling変換、法上の階乗を使い、rank別計数を基底変換する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-combinatorial-coefficients

習得する技能

  • 冪基底と下降階乗基底の係数をStirling数で変換し、目的のrank別計数列を構成できる。
  • 素数pのもとでn,kをp進展開し、Lucasの定理 C(n,k)=∏C(n_i,k_i) mod pで、n≥pでも階乗の零除算を避けて計算できる。
  • 生成ベクトルのspan条件をrank別の部分空間数へ変換し、有限体上のGaussian binomial係数で各rankの寄与を数えられる。
  • 選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: 組合せを生成関数へ符号化する、factorial convolutionによる多項式Taylor shift、Prüfer code・次数制約付きlabel木、鏡像法・reflection principle。

選び方を通常・Gaussian二項係数で整理し、必要ならStirling変換でrank別計数を基底変換する。

このUnitでは扱わないもの

  • 重なりを交互加減する包除・Möbius反転。

根拠