A NOTE ON THE BINOMIAL DROP POLYNOMIAL OF A POSET

[摘要] Suppose (P, <) is a poset of size n and pi: P --> P is a permutation. We say that pi has a drop at x if pi(x) < x. Let delta(P)(k) denote the number of pi having k drops, 0 less-than-or-equal-to k < n, and define the drop polynomial DELTA(P)(lambda) by [GRAPHICS] Further, define the incomparability graph I(P) to have vertex set P and edges whenever i and j are incomparable in P, i.e., neither i < j nor j < i holds. In this note we give a short proof that DELTA(P)(lambda) is equal to the chromatic polynomial of I(P). (C) 1994 Academic Press, Inc.

[发布日期] 1994-05-01