Basic structures
Generating functions
Proof techniques
Combinatorial identities
Polytopes
The zeta polynomial of a finite partially ordered set counts the number of multichains (also known as “weakly increasing sequences”) of length in .
By a multichain of length in , we mean a sequence of elements , which can be identified with an order-preserving function from the linear order into . To see that
defines a polynomial in ,1 first observe that any function factors as a surjection from onto some (where ), followed by an injection from to . The total number of order-preserving functions from to can therefore be calculated explicitly as
where is the number of chains in (i.e., injective order-preserving functions from to ), and where is the length of the longest chain. Hence is a polynomial of degree equal to the length of the longest chain in .
The zeta polynomial of is
For example, evaluating the polynomial at and confirms that contains 3 points and 6 intervals, while evaluating it at confirms that there are 10 order-preserving functions from to itself.
The zeta polynomial of the 5-element poset
is . Evaluating at , we compute that contains 14 distinct intervals.
The order polynomial is related to the zeta polynomial by the equation
where is the lattice of lower sets in . This can be seen as a consequence of the currying isomorphisms
together with the isomorphisms .
Using the formalism of incidence algebras, the zeta polynomial has a simple expression in terms of the zeta function of (defined by if and otherwise):
where is the -fold convolution product of . (In other words, if we view the zeta function as a square matrix, then the zeta polynomial is the sum of the entries in its -fold matrix product.) This follows immediately from the definition of the convolution product,
since computes the number of multichains of length in from to .
As a special case, if has both a bottom element 0 and a top element 1, then
since an arbitrary multichain of length can be extended to a multichain of length between 0 and 1.
Note that the definition we use here for has an index shift from the definition that seems to be more standard in combinatorics. For example, the definition in (Stanley, 3.12) counts multichains of length rather than of length . Accordingly, one should apply a substitution to get some of the properties stated here to match equivalent results in the literature. ↩
Last revised on August 26, 2018 at 12:21:27. See the history of this page for a list of all contributions to it.