Library Checker - Chromatic Polynomial

計算できることの説明は補間多項式を使うと楽だが、除算を使わない方法も重要かもしれない。

議論

一定の条件を満たす$ N要素 SPS$ s(\bm{x})について、ある多項式$ P(y)が存在して、任意の非負整数$ nで$ \lbrack\bm{x}\rbrack s^n=P(n)を満たす。

$ s(\bm{x})の係数が非負整数であると仮定すれば、この「条件」に実用上

定数項は$ 1である

を課せる。 $ 2 以上なら$ nに対して増加が指数的になり、$ 0なら$ P(n)=0($ N\lt n)となって不都合である。

アルゴリズム

$ \lbrack\bm{x}\rbrack s^nを計算して補間する代わりに、$ sの定数項を$ 0に変えてから$ w _ n=\lbrack\bm{x}\rbrack s^n/n!を計算し、$ P(y)=\sum _ {k=0}^{N}w _ ny^{\underline{k}}とする。($ y^{\underline{k}}=y(y-1)\cdots (y-k+1))

定数倍削減

普通に power projection で$ w _ n=\lbrack\bm{x}\rbrack s^n/n!を計算する代わりに、 power projection の重みを$ sの上位半分で設定すれば残り半分についての計算で必要な値が得られる。