Dénombrement des ordres étagés (Q762485)

A tiered order relation is one in which every maximal chain has the same length which is called the height of the relation. The author has found a recurrence relation for t(h,m,n), the number of tiered order relations with height h and exactly m maximal elements that can be defined on an n- set. In fact, \(t(h,m,n)=\left( \begin{matrix} n\\ m\end{matrix} \right)\sum^{n- m}_{k=1}c(m,k)t(h-1,k,n-m)\) where c(m,k) is the number of bipartite graphs on an m-set and a k-set in which every vertex has positive degree. It is easy to show by the inclusion-exclusion formula that \(c(m,k)=\sum^{k}_{i=0}(-1)^ i\left( \begin{matrix} k\\ i\end{matrix} \right)(2^{k-i}-1)^ m.\) Let \(t(n)=\sum_{h,m}t(h,m,n).\) The author has calculated t(n) for \(n=1,...,11\), and observed that t(n) is alternately congruent to 1 and 3 (mod 6). Whether this is just a coincidence, or indication of a general result is an open question. A similar observation is made for the number of order relations on an n- set. (The reviewer has proved the first conjecture.)