Notes on Whitney Numbers of the Second Kind for the Star Poset

摘要

The Whitney numbers of the second kind W_0, W_1, W_2, ..., for a ranked poset are defined in such a way that W_i is the number of elements of rank i. The star poset is a ranked poset where (1) the elements are those of the symmetric group S_n; and (2) the partial order is defined such that u < v if d(e,u) < d(e,v) where e is the identity 12 • • • n and d(e, u) is the rank of u where d(s, t) is the shortest distance between s and t. In [4], the Whitney numbers of the second kind for the star poset are studied and explicit formula is derived. In particular, a recurrence relation is obtained to compute the table of Whitney numbers for the star poset for different n's. Their approach used generating functions and other algebraic techniques and is quite involved. In this paper, we study the problem from a graph theoretical point of view, deriving the same recurrence used to compute the table of Whitney numbers in a much simpler way and at the same time, deriving several interesting properties of the underlying graphs.