A chromatic partition polynomial

✍ Scribed by Einar Steingrímsson

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 618 KB
• Volume: 180
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00125-8

✦ Synopsis

A polynomial in two variables is defned by C,(x,t)= ~-~cn,, Z( a~,x)tl~l, where Hn is the lattice of partitions of the set { I, 2 ..... n}, G~ is a certain interval graph defined in terms of the partition 7r, z(G~,x) is the chromatic polynomial of G~ and Inl is the number of blocks in n. It " t ~-~i=0 (~-ik)S(n'i)(x)i' where S(n,i) is the Stirling number of is shown that Cn(x, t)= ~k=0 k k the second kind and (x)i = x(x-1)... (x-i + 1). As a special case, Cn(-1,-t) = An(t), where A~(t) is the nth Eulerian polynomial. Moreover, An(t)= ~-~cn,, a"tl~P, where a~ is the number of acyclic orientations of G..

R6sum6

On d6finit un polyn6me en deux variables par C.(x,t)= ~.etl,, Z( G~,x)tl~q, off H~ est le treillis des partitions de l'ensemble { 1,2 ..... n}, G. est un certain graphe d'intervalles d6fini en termes de la partition n, )~ (G~,x) est le polyn6me chromatique de G~ et Ircl est le nombre de n n--i blocs de 7t. On montre que Cn(x,t)= ~--~k=0 tk ~=0 (n--k) S(n'i)(x)i Off S(r/,i) est le nombre de Stirling de deuxi6me esp~ce et (x)i =x(x-1).-. (x-i + 1). En particulier, Cn(-1,-t) =A,(t), off An(t) est le n-i~me polyn6me eul6rien. De plus, An(t)= ~-~cn,, a~tl~l, off an est le nombre d'orientations acycliques de G~.