Combinatorial Applications of Ordinal Sum Decompositions

For any double sequence \((q_{k,n})\) with \(q_{k,0} = 0\), the “summatorial sequence” \((P_{k,n}) = \sum(q_{k,n})\) is defined by \(p_{0,0} = 1\) and \(P_{k,} = \sum_{j=0}^k \sum_{m=1}^n q_{ j,m}P_{k-j,n-m}\) If \(q_{k,n} = 0\) for \(k < n-1\) then there exists a unique sequence \((c_j)\) satisfying the recurrence \(P_{k,n} = \sum_{j=0}^k c_j P_{k-j,k-j,n-m}\) for \(k < n\). We apply this combinatorial recursion to certain counting functions on finite posets. For example, given a set \(A\) of positive integers, let \(P_{k,n}\) denote the number of unlabeled posets with \(n\) points and exactly \(k\) antichains whose cardinality belongs to \(A\), and let \(q_{k,n}\) denote the corresponding number of ordinally indecomposable posets. Then \((P_{k,n})\) is the summatorial sequence of \((q_{k,n})\). If \(2 \in A\) then \((P_{k,n})\) enjoys the above recurrence for \(k < 1\). In particular, for fixed \(k\), there is a polynomial \(p_k\) of degree \(k\) such that \(P_{n,k} = p_k(n)\) for all \(n \geq k\), and \(p_{k,n}\) is asymptotically equal to \(\binom{n-1}{k}\). For some special classes \(A\) and small \(k\), we determine the numbers \(c_k\) and the polynomials \(p_k\) explicitly. Moreover, we show that, at least for small \(k\), the remainder sequences \(p_{k,n} – p_k(n)\) satisfy certain Fibonacci recursions, proving a conjecture of Culberson and Rawlins. Similar results are obtained for labeled posets and for naturally ordered sets.