Dénombrement des ordres étagés
type: Item
instance of: scholarly article
title: Dénombrement des ordres étagés
zbMATH Open document ID: 0558.05004
DOI: 10.1016/0012-365X(85)90137-2
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: 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.)
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 3889532
zbMATH Keywords: tiered order relation
zbMATH Keywords: recurrence relation
zbMATH Keywords: number of bipartite graphs
author: Germain Kreweras
reviewed by: David A. Klarner
MaRDI profile type: Publication
cites work: The number of graded partially ordered sets
cites work: Q5605912
cites work: A Machine Representation of Finite T 0 Topologies
description: scientific article; zbMATH DE number 3889532