Name
Abstract | ||
|---|---|---|
Let p kn denote the number of unlabeled posets with n points and k unrelated pairs. We show that for k < n , these numbers satisfy a recursion formula of the form P kn = Σ k j =0 c j p k − j , n − j −1 , where the coefficients c j can be computed if the numbers q jm of all ordinally indecomposable posets with m points and j unrelated pairs are known for m − 1⩽ j ⩽ k . The crucial lemma for the proof states that q jm =0 for j < m − 1. From the recursion formula it follows that p kn is a polynomial of degree k in the variable n and that P kn ≥ n−1 k with asymptotic equality for fixed k . For small values of k , we determine these polynomials explicitly. At the other end of the scale, we find that q n−1,n = 2 n −3 for n ⩾3. Similar results are obtained for the number of labeled posets with a fixed linear extension and a given number of unrelated pairs. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0012-365X(92)90131-X | Discrete Mathematics |
Keywords | Field | DocType |
incomparable pair,partially ordered set | Recurrence formula,Discrete mathematics,Combinatorics,Polynomial,Enumeration,Linear extension,Indecomposable module,Partially ordered set,Mathematics,Lemma (mathematics),Recursion | Journal |
Volume | Issue | ISSN |
105 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
2 | 0.70 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcel Erné | 1 | 29 | 10.77 |