準多項式のソースを表示

{{for|準多項式で表される計算時間|w:Quasi-polynomial time}}
'''準多項式'''（じゅんたこうしき、quasi-polynomial、pseudo-polynomial）は[[多項式]]を一般化したものである。多項式の係数は[[環 (数学)|環]]の元になっているが、準多項式の係数は整数周期を持つ[[周期関数]]である。準多項式は[[組合せ数学]]の多くの理論でさまざまな対象の列挙子として用いられる。

準多項式は <math>q(k) = c_d(k) k^d + c_{d-1}(k) k^{d-1} + \cdots + c_0(k)</math> と表される。ここで <math>c_{i}(k)</math> は整数周期を持つ周期関数である。<math>c_d(k)</math> が恒等的に 0 でなければ ''q'' の次数は ''d'' である。また <math>n \equiv i \bmod s</math> で <math>f(n) = p_i(n)</math> であるような多項式 <math>p_0, \dots, p_{s-1}</math> が存在するとき、関数 <math>f \colon \mathbb{N} \to \mathbb{N}</math> は準多項式である。多項式 <math>p_i</math> を ''f'' の成分という。

== 例 ==
* [[有理点]] <math>v_1,\dots,v_n</math> を頂点とする ''d'' 次の[[ポリトープ]] ''P''について、''tP'' を <math>tv_1,\dots,tv_n</math> の凸包と定義する。関数 <math>L(P,t) = \#(tP \cap \mathbb{Z}^d)</math> は ''t'' による ''d'' 次の準多項式である。このとき ''L(P,t)'' は <math>\mathbb{N} \to \mathbb{N}</math> 関数である。これはウジェーヌ・エルハート（Eugène Ehrhart）にちなみ'''エルハート準多項式'''と呼ばれる。
* 2つの準多項式 ''F''、''G'' の[[畳み込み|合成積]]は
:<math>(F*G)(k) = \sum_{m=0}^k F(m)G(k-m)</math>
と定義される。これは次数 <math>\le \deg F + \deg G + 1</math> の準多項式になっている。

== 関連項目 ==
* [[エルハート多項式]]

== 参考文献 ==
* [[w:Richard P. Stanley|Stanley, Richard P.]] (1997). [http://www-math.mit.edu/~rstan/ec/ ''Enumerative Combinatorics'', Volume 1]. Cambridge University Press.  ISBN 0-521-55309-1, 0-521-56069-1.

{{Math-stub}}
{{DEFAULTSORT:しゆんたこうしき}}
[[Category:多項式]]
[[Category:組合せ論]]
[[Category:代数的組合せ論]]
[[Category:数学に関する記事]]