A chromatic partition polynomial |
| |
Authors: | Einar Steingrí msson, |
| |
Affiliation: | aMatematiska Institutionen, Chalmers Tekniska Högskola, Göteborgs Universitet, 412 96 Göteborg, Sweden |
| |
Abstract: | A polynomial in two variables is defined by Cn(x,t)=ΣπΠnx(Gπ,x)t|π|, where Πn is the lattice of partitions of the set {1, 2, …, n}, Gπ is a certain interval graph defined in terms of the partition gp, χ(Gπ, x) is the chromatic polynomial of Gπ and |π| is the number of blocks in π. It is shown that , where S(n, i) is the Stirling number of the second kind and (x)i = x(x − 1) ··· (x − i + 1). As a special case, Cn(−1, −t) = An(t), where An(t) is the nth Eulerian polynomial. Moreover, An(t)=ΣπΠnaπt|π| where aπ is the number of acyclic orientations of Gπ. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|