Whitney numbers of the second kind for the star poset
A rank r on a (finite) poset (p,\(\leq)\) is a function with non-negative integer values such that if \(a\leq^*b\) (a is covered by b), then \(r(b)=r(a)+1\). The Cayley graph G(n) of the symmetric group \(V(n)=S_ n\) relative to the set of transpositions \(T=\{(1,n),...,(n-1,n)\}\) has an edge-set \(E(n)=\{e=(p_ 1,p_ 2)|\) \(p_ 1\pi =p_ 2\) for some \(\pi\in T\}\). The star-poset is defined on V(n) by assigning \(p_ 1\leq^*p_ 2\) iff \(e=(p_ 1,p_ 2)\in E(n)\) and \(d(p_ 1,I)<d(p_ 2,I)\), where I is the identity of \(S_ n\) and d is the usual graph distance. If a poset is ranked, the number of elements of rank k is denoted by \(W_ k\) and called a Whitney number of the second kind. If \(W_{n,k}\) is \(W_ k\) for G(n), then it is shown, after some detailed computations, which are structurally revealing, that if \(W_ n(X)=\sum W_{n,k}X^ k\), then \(G(Y)=(1-XY)^{-X-1}e^{Y-X^ 2Y}\) where \(G(Y)=\sum W_ k(X)Y^{k-1}/(k-1)!\) is the exponential generating function for \(\{W_ n(X)\}\). Using standard techniques and special information on the poset through a series of technical lemmas, a recurrence (Theorem 3.9) is obtained whence the formula is established. Combining subsets of ingredients obtained to the point of the derivation of the formula for G(Y) in a variety of ways, several other corollaries and formulas are obtained as well. Star posets are thus a nice class of interesting ranked posets which can be considered as combinatorially well understood examples. This paper is therefore certainly a useful addition to this type of literature.
scientific article; zbMATH DE number 4158686