準多項式
準多項式(じゅんたこうしき、quasi-polynomial、pseudo-polynomial)は多項式を一般化したものである。多項式の係数は環の元になっているが、準多項式の係数は整数周期を持つ周期関数である。準多項式は組合せ数学の多くの理論でさまざまな対象の列挙子として用いられる。
準多項式は q ( k ) = c d ( k ) k d + c d − 1 ( k ) k d − 1 + ⋯ + c 0 ( k ) {\displaystyle q(k)=c_{d}(k)k^{d}+c_{d-1}(k)k^{d-1}+\cdots +c_{0}(k)} と表される。ここで c i ( k ) {\displaystyle c_{i}(k)} は整数周期を持つ周期関数である。 c d ( k ) {\displaystyle c_{d}(k)} が恒等的に 0 でなければ q の次数は d である。また n ≡ i mod s {\displaystyle n\equiv i{\bmod {s}}} で f ( n ) = p i ( n ) {\displaystyle f(n)=p_{i}(n)} であるような多項式 p 0 , ... , p s − 1 {\displaystyle p_{0},\dots ,p_{s-1}} が存在するとき、関数 f : N → N {\displaystyle f\colon \mathbb {N} \to \mathbb {N} } は準多項式である。多項式 p i {\displaystyle p_{i}} を f の成分という。