Posets with the Same Number of Order Ideals of Each Cardinality:
a problem from Stanley's "Enumerative Combinatorics"
Fulbright Distinguished Scholar, Oxford University
Let $P$ be an n-element partially ordered set (poset). A subset
$I$ is an "order ideal" if, for all $i\in I$ and $p\in P$, if $p\le i$
then $p\in I$. The collection of all order ideals, partially ordered by
inclusion, is closed under unions and intersections, and hence
forms a "distributive lattice."
For $k\in\Bbb N$, let $f_k(n)$ be the number of non-isomorphic
posets $P$ such that, if $1\le i\le n-1$, then $P$ has exactly $k$ order
ideals of cardinality $i$.
In "Enumerative Combinatorics" (the classic 1986 text of the
Massachusetts Institute of Technology combinatorialist Richard P.
Stanley), an unsolved problem is to determine
the generating function for $f_k(n)$. Due to an observation of Paul
Edelman, it suffices to consider the case $k=3$.
We determine the all the posets with the prescribed property, by
considering their corresponding distributive lattices. We use a result of
the author and Stefan E. Schmidt (obtained in response to another issue
raised by Stanley concerning group actions on posets) which says whether
or not a poset is isomorphic to a distributive lattice if all of its rank
3 intervals are.
Finally, we show how these results can be used to solve a problem
of Ivo Rosenberg, dating back to the 1981 Banff Conference on