A chromatic partition polynomial (Q1381837)

Let \(|\pi|\) denote the number of blocks in a partition \(\pi\) of \([n]= \{1,2, \dots, n\}\). Let \(p=a_1 a_2 \dots a_n\) be a permutation of \([n]\). A descent block of \(p\) is a maximal decreasing continuance subword \(a_ia_{i+1} \dots a_j\) of \(p\). The \(n\)th Eulerian polynomial \(A_n(t)\) (for \(n=0,1,2,\dots)\) is defined by \[ \sum_{k\geq 0} k^nt^k= {A_n (t) \over (1-t)^{n+1}}. \] The \(i\)th coefficient of \(A_n(t)\) is the number of permutations of \([n]\) with \(i-1\) descents. The first main result of this paper is: \[ A_n(t)= \sum_{\pi\in \Pi_n} a_\pi t^{ | \pi|} \] where \(a_\pi\) is the number of acyclic orientations of \(G_\pi\), a certain interval graph defined in terms of the partition \(\pi\) of \([n]\), and \(\Pi_n\) is the lattice of partitions of \([n] \). A polynomial in two variables is defined by \[ C_n (x,t)= \sum_{\pi\in \Pi_n} \chi (G_\pi,x) t^{| \pi|} \] where \(\chi (G_\pi,x)\) is the chromatic polynomial of \(G_\pi\). The second main result of this paper is: \[ C_n(x,t) =\sum^n_{k=0} t^k\sum^k_{i=0} {n-i \choose n-k} S(n,i) (x)_i, \] where \(S(n,i)\) is the Stirling number of the second kind and \((x)_i= x(x-1) \dots (x-i+1)\). As a special case, \(C_n(-1,-t) =A_n(t)\). The concepts involved in this paper are clearly explained with the help of examples.