Journal of Integer Sequences, Vol. 6 (2003), Article 03.4.3

Counting Biorders

Julie Christophe, Jean-Paul Doignon, and Samuel Fiorini
Université Libre de Bruxelles
Département de Mathématique, c.p. 216
Bd du Triomphe
B-1050 Bruxelles
Belgium

Abstract: Biorders were introduced first as Guttman scales and then as Ferrers relations. They are now well recognized in combinatorics and its applications. However, it seems that no procedure besides plain enumeration was made available for obtaining the number of biorders from an m-element set to an n-element set. We establish first a double-recurrence formula for computing this number, and then two explicit formulas involving Stirling numbers of the second kind. Our methods do not seem to extend to other, similar structures. For instance, interval orders on a finite set are exactly the irreflexive biorders on that set. To our knowledge, no direct formula is available for deriving their number.

(Concerned with sequences A006531 A000108 A022493.)

Received February 17 2003; revised version received October 27 2003. Published in Journal of Integer Sequences December 12 2003.