Counting Biorders

Julie Christophe^{1}, Jean-Paul Doignon^{2}, and Samuel Fiorini^{3}

Université Libre de Bruxelles Département de Mathématique, c.p. 216 Bd du Triomphe B-1050 Bruxelles Belgium

                  juchrist@ulb.ac.be
                   doignon@ulb.ac.be
                  sfiorini@ulb.ac.be

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.

1 Introduction

Throughout the text, X and Y denote finite sets of respective cardinalities m and n. A biorder from X to Y is any relation from X to Y that admits a step-like tableau, meaning: there exists some ordering x_{1}, x_{2}, …, x_{m} of the elements in X and some ordering y_{1}, y_{2}, …, y_{n} of the elements in Y such that the corresponding (boolean) tableau of the relation has its 0’s separated from its 1’s by a staircase, as in the following example:

1J. C. is a Fellow of the Fonds pour la Formation à la Recherche dans l’Industrie et dans l’Agriculture.

2Corresponding author.

3S. F. is supported by a Fellowship of the Belgian American Educational Foundation.

\begin{aligned}& y_{1} & y_{2} & y_{3} & y_{4} & y_{5} & y_{6} & y_{7} \\ x_{1} & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ x_{2} & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ x_{3} & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ x_{4} & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ x_{5} & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{aligned}  (1)

Also, a relation R from X to Y is a biorder if and only if it satisfies any of the following equivalent conditions:

1. for all w, x ∈ X and y, z ∈ Y:

(wRy and xRz) implies (wRz or xRy);  (2)

2. all subsets R(x) = {y ∈ Y | xRy}, for x ∈ X, form a chain of subsets of Y (repetitions being allowed);

3. all subsets R^{−1}(y) = {x ∈ X | xRy}, for y ∈ Y, form a chain of subsets of X;

4. no tableau for R contains a subtableau of the form

( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )  or  ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) .  (3)

These simple conditions, and several other ones, were established when biorders were first introduced in psychology as ‘scales’ by Guttman [7], and then in mathematics as ‘Ferrers relations’ by Riguet [10]. For a survey of the early history of biorders, see Monjardet [9]. Besides their use in social sciences, biorders have proved useful in a variety of situations. For instance, they come as a convenient, technical tool for Yannakakis [12], or they are used as the 1-dimensional constituents in a dimensional theory of relations by Cogis [2] and Doignon, Ducamp and Falmagne [4] (the latter reference introduced the term ‘biorder’).

Although biorders are by now well assimilated in some chapters of combinatorics and its applications, it seems that no direct method for counting biorders was ever published. We will provide three formulas for obtaining the number of biorders from an m-element set to an n-element set. A first formula captures a double-recurrence approach. Then an explicit formula is derived which relies on Stirling numbers of the second kind. Still another formula is established along another line of reasoning, which also makes use of the same Stirling numbers.

Our method does not seem to be applicable to related, similar structures. For instance (see, e.g., Fishburn [5] for these concepts), interval orders on a finite set Z are exactly the irreflexive biorders from Z to Z, while semiorders are the interval orders satisfying also for x, y, z, t ∈ Z

(xRy and yRz) implies (xRt or tRz).  (4)

Formulas for the number of semiorders on an n-element set are given in Chandon, Lemaire and Pouget [1] (see also Sequence A006531 in the On-Line Encyclopedia of Integer Sequences [11]), but apparently no explicit formula is known in the literature for the similar number of interval orders.

Notice that all counts mentioned so far are for labeled structures. As regards counting up to isomorphism, the case of semiorders leads to the Catalan number \frac{1}{n+1} \binom{2n}{n} (see [5] or Sequence A000108 [11]), while a polynomial-time algorithm for computing the number of isomorphism types of interval orders is due to Haxell, McDonald and Thomason [8] (Sequence A022493 [11]). On the other hand, the case of biorders from X to Y is easy in case X∩Y = ∅: there are \binom{m+n}{n} isomorphism types of biorders from an m-element set X to a disjoint nelement set Y. To prove this, we need only indicate how to count step-like tableaus, and it suffices to point out that the separating staircase is made of m + n strokes, of which m are vertical and n are horizontal.

2 Double Recurrence

Let us denote by B(m, n) the quantity we are interested in, that is the number of biorders from the m-element set X to the n-element set Y. Assuming X ∩ Y = ∅ does not set any restriction here, because of the duplication construction of Doignon, Ducamp and Falmagne [4]; the reader might find it helpful to assume X ∩ Y = ∅. The following proposition shows how to compute numbers B(m, n) by a double recurrence.

Proposition 1 For m > 0 and n > 0, we have

B(m, n) = ∑_{j=0}^{m−1} ∑_{k=0}^{n−1} \binom{m}{j} \binom{n}{k} B(j, k)  (5)

and

B(m, 0) = B(0, n) = 1,  (6)

together with

B(0, 0) = 2.  (7)

Proof. A tableau is said to be of Type 0 if it has a column of 0’s, and of Type 1 if it has a row of 1’s. Correspondingly, a biorder from X to Y is of Type 0 if at least one set R^{−1}(y) is empty, where y ∈ Y; denote by B_{0}(m, n) the number of biorders of Type 0. Similarly, a biorder from X to Y is of Type 1 if R(x) = Y holds for at least one element x in X; denote by B_{1}(m, n) the number of such biorders. Notice the equality

B_{0}(m, n) = B_{1}(n, m),  (8)

which follows from the following two facts: first, taking the complement of the converse of a biorder from X to Y always gives a biorder from Y to X, second this operation transforms a Type 0 tableau into a Type 1 tableau.

Moreover, from the definition of biorders, we get at once

B(m, n) = B_{0}(m, n) + B_{1}(m, n).  (9)

To obtain recurrence relations first for B_{1}(m, n) and then for B(m, n), we now suppose m > 0 and n > 0 and fix some orderings of X and Y. Thus any biorder (even, any relation) corresponds to exactly one tableau.

Any Type 1 biorder is univocally formed by (i) selecting j among the m rows, for some j with 0 ≤ j < m, (ii) then setting all entries in the m − j other rows to 1, and (iii) finally specifying some Type 0 tableau on the selected j rows. This shows

B_{1}(m, n) = ∑_{j=0}^{m−1} \binom{m}{j} B_{0}(j, n) = ∑_{j=0}^{m−1} \binom{m}{j} B_{1}(n, j).  (10)

Now the following computations based on Equations (8)–(10) give us Equation (5) in the statement:

B(m, n) = B_{0}(m, n) + B_{1}(m, n)
= B_{1}(n, m) + B_{1}(m, n)
= ∑_{k=0}^{n−1} \binom{n}{k} B_{1}(m, k) + ∑_{j=0}^{m−1} \binom{m}{j} B_{1}(n, j)

= ∑_{k=0}^{n−1} \binom{n}{k} ∑_{j=0}^{m−1} \binom{m}{j}B_{0}(j, k) + ∑_{j=0}^{m−1} \binom{m}{j} ∑_{k=0}^{n−1} \binom{n}{k}B_{1}(j, k)

= ∑_{j=0}^{m−1} ∑_{k=0}^{n−1} \binom{m}{j} \binom{n}{k} B(j, k).

Finally, the values in Equations (6)–(7) are chosen to generate the correct expressions B(m, 1) = 2^{m} and B(1, n) = 2^{n}.

With a program implementing the formulas from Equation (5), we computed the values of B(m, n) shown in Table 1. Notice B(m, n) = B(n, m) (which holds because the converse of a biorder is always a biorder). The first two rows in Table 1 are easily explained. For m = 1, we have B(1, n) = 2^{n}. For m = 2, the tableaux of biorders are exactly those tableaux not containing both a column {0 \atop 1} and a column {1 \atop 0}. Hence their number satisfies B(2, n) = 2·3^{n}−2^{n}.

m\n 1 2 3  4  5  6  7  8
1  2 4 8  16  32  64  128  256
2  14 46 146  454  1 394  4 246  12 866
3  230 1 066 4 718  20 266  85 310  354 106
4  6 902 41 506  237 686 1 315 666  7 107 302
5  329 462 2 441 314 17 234 438 117 437 746
6  22 934 773 202 229 266 1 701 740 006

Table 1: Some values of B(m, n).

3 A First Explicit Formula

Some hand computations exploiting the double-recurrence in Proposition 5 strongly suggest to write B(m, n) as a weighted sum of n-th powers. To identify the coefficients, we use the Stirling numbers of the second kind, here denoted as S(m, j) (see, e.g., [6] where the notation \left\{{m \atop j}\right\} is used). Remember that S(m, j), the number of ways of partitioning an m-element set into j classes, equals

S(m, j) = \frac{1}{j!} ∑_{i=1}^{j}(−1)^{j−i} \binom{j}{i} i^{m}.  (11)

Here are some other properties of these numbers, for m > 0:

S(m, j) = 0 when j < 1 or m < j,  (12)
S(m, m) = S(m, 1) = 1,  (13)

and

S(m, u) = S(m − 1, u − 1) + u S(m − 1, u).  (14)

We will also need (see [6], Equation (6.17) and on page 264, the formula for x^{n}, with x set to 1): for 1 ≤ j ≤ m,

S(m, j) = ∑_{k=j}^{m} \binom{m}{k} (−1)^{m−k} S(k + 1, j + 1),  (15)

and for m ≥ 1,

1 = ∑_{t=1}^{m} (−1)^{m+t} t! S(m, t).  (16)

Proposition 2 For m > 0 and n ≥ 0, we have

B(m, n) = ∑_{t=1}^{m} (−1)^{m+t} t! S(m, t) (t + 1)^{n}.  (17)

Proof. Setting for m > 0 and m ≥ t ≥ 1

b_{m,t} = (−1)^{m+t} t! S(m, t),  (18)

and also for convenience b_{m,m+1} = 0, we first record some properties of the numbers b_{m,n}:

b_{m,1} = (−1)^{m+1};  (19)
b_{m,m} = m! ;  (20)
b_{m,t} = ∑_{j=t−1}^{m−1} \binom{m}{j}(b_{j,t−1} − b_{j,t}),  for 1 < t < m.  (21)

Equation (19) follows from S(m, 1) = 1, and Equation (20) from S(m, m) = 1. More computations are needed for the next equation. Starting from the right-hand side of Equation (21), we have (in view of Equations (14) and (15))

∑_{j=t−1}^{m−1} \binom{m}{j}(b_{j,t−1} − b_{j,t})

= ∑_{j=t−1}^{m−1} \binom{m}{j}(−1)^{j+t−1}(t − 1)! (S(j, t − 1) + t S(j, t))

= (t − 1)! (−1)^{t−1} ∑_{j=t−1}^{m−1} \binom{m}{j} (−1)^{j} S(j + 1, t)
= (t − 1)! (−1)^{t−1} (−1)^{m} (S(m, t − 1) − S(m + 1, t))
= (−1)^{m+t} (t − 1)! t S(m, t)
= b_{m,t}

which establishes Equation (21).

Next we establish by double recurrence on m > 0 and n ≥ 0 the equality in the thesis, rephrased as:

B(m, n) = ∑_{t=1}^{m} b_{m,t} (t + 1)^{n}.  (22)

This equality holds for sure in case m = 1 because of B(1, n) = 2^{n} and Equation (19); it also holds in case n = 0, in view of B(m, 0) = 1 for m ≠ 0 and Equation (16).

Supposing now that the following equation holds for 1 ≤ j < m and 0 ≤ k < n

B(j, k) = ∑_{t=1}^{j} b_{j,t} (t + 1)^{k},  (23)

we proceed to infer Equation (22). After having inserted Equation (23) into Equation (5), we get successively

B(m, n)
= ∑_{j=0}^{m−1} ∑_{k=0}^{n−1} \binom{m}{j} \binom{n}{k} B(j, k)

= B(0, 0) + ∑_{k=1}^{n−1} \binom{n}{k} B(0, k) + ∑_{j=1}^{m−1} ∑_{k=0}^{n−1} \binom{m}{j} \binom{n}{k} ∑_{t=1}^{j} b_{j,t} (t + 1)^{k}

= 2 + (2^{n} − 2) + ∑_{j=1}^{m−1} \binom{m}{j} ∑_{t=1}^{j} b_{j,t} ∑_{k=0}^{n−1} \binom{n}{k} (t + 1)^{k}

= 2^{n} + ∑_{j=1}^{m−1} \binom{m}{j} ∑_{t=1}^{j} b_{j,t}(1 + t + 1)^{n} − ∑_{j=1}^{m−1} \binom{m}{j} ∑_{t=1}^{j} b_{j,t}(t + 1)^{n}.

Then replacing t + 1 with t in the second term, we have

B(m, n)
= 2^{n} + ∑_{j=1}^{m−1} \binom{m}{j} ∑_{t=2}^{j+1} b_{j,t−1} (t + 1)^{n} − ∑_{j=1}^{m−1} \binom{m}{j} ∑_{t=1}^{j} b_{j,t}(t + 1)^{n}

= (1 − ∑_{j=1}^{m−1} \binom{m}{j} b_{j,1}) 2^{n} + ∑_{j=1}^{m−1} \binom{m}{j} ∑_{t=2}^{j+1} (b_{j,t−1} − b_{j,t}) (t + 1)^{n}

and using b_{j,j+1} = 0

B(m, n)
= (1 − ∑_{j=1}^{m−1} \binom{m}{j} (−1)^{j+1}) 2^{n} + ∑_{t=2}^{m} (t + 1)^{n} ∑_{j=t−1}^{m−1} \binom{m}{j} (b_{j,t−1} − b_{j,t})
= (−1)^{m+1} 2^{n}

+ ∑_{t=2}^{m−1} (t + 1)^{n} ∑_{j=t−1}^{m−1} \binom{m}{j} (b_{j,t−1} − b_{j,t})

+m b_{m−1,m−1} (m + 1)^{n}.

Now Equations (19), (21), (20) lead to

B(m, n) = b_{m,1}2^{n} + ∑_{t=2}^{m−1} b_{m,t} (t + 1)^{n} + b_{m,m} (m + 1)^{n}

which is Equation (22). This completes the proof by recurrence.

Replacing the Stirling numbers in Equation (17) with their expressions from Equation (11), we derive the more explicit formula

B(m, n) = ∑_{i=1}^{m} (−1)^{m−i} i^{m} ∑_{t=i}^{m} \binom{t}{i} (t + 1)^{n}.  (24)

Another reformulation is obtained by introducing the number W(m, k) = k! S(m, k) of weak orders with k classes on an m-element set:

B(m, n) = ∑_{t=1}^{m} (−1)^{m+t} W(m, t) (t + 1)^{n}.  (25)

All of these formulas for B(m, n) are alternating sums. We now turn to another way of counting, which will provide us with a sum of positive terms.

4 A Second Explicit Formula

In view of the properties collected in the Introduction, any biorder B from X to Y determines a weak order B_{X} on X and a weak order B_{Y} on Y, defined through

x B_{X} x′ ⟺ B(x) ⊆ B(x′), and y B_{Y} y′ ⟺ B^{−1}(y) ⊆ B^{−1}(y′).  (26)

Proposition 3 Given a biorder B from X to Y, the two weak orders B_{X} and B_{Y} have their numbers of equivalence classes differing by at most one. Conversely, any two weak orders on respectively X and Y which have the same number of equivalence classes derive in this way from exactly two biorders from X to Y. Also, if two weak orders on respectively X and Y have their numbers of equivalence classes differing by 1, then they derive from exactly one biorder from X to Y.

Proof. All assertions can be easily checked by considering a step-like tableau for the (given or to-be-constructed) biorder B.

We now derive a second explicit formula for the number of biorders from X to Y, which in case |X| = |Y | was first obtained by Destrée [3].

Proposition 4 The number B(m, n) of biorders from X to Y, where |X| = m and |Y | = n, equals

B(m, n) = ∑_{k=1}^{m} k! (k − 1)! S(m, k) (S(n + 1, k) + k S(n + 1, k + 1)).  (27)

Remark that, contrary to Equation (17), we have here a sum of positive terms. On the other hand, there are more summations here, because each Stirling number requires one.

Proof. ¿From Proposition 3, we derive

B(m, n) =

∑_{k=1}^{m} k! S(m, k) ((k − 1)! S(n, k − 1) + 2 k! S(n, k) + (k + 1)! S(n, k + 1)).

Applying Equation (14), we get Equation (27).

In the particular case m = n, we have [3]

B(m, m) = 2 ∑_{k=1}^{m} (k!)^{2} S(m, k) S(m + 1, k + 1).  (28)

Returning to the general case, we conclude that the number of biorders both equals either side of

∑_{t=1}^{m} (−1)^{m+t} t! S(m, t) (t + 1)^{n} =

∑_{k=1}^{m} k! (k − 1)! S(m, k) (S(n + 1, k) + k S(n + 1, k + 1))  (29)

and is the solution to the double recurrence, for m > 0 and n > 0,

B(m, n) = ∑_{j=0}^{m−1} ∑_{k=0}^{n−1} \binom{m}{j} \binom{n}{k} B(j, k),  (30)

with initial conditions

B(m, 0) = B(0, n) = 1 and B(0, 0) = 2.  (31)

References

[1] J.-L. Chandon, J. Lemaire, and J. Pouget, Dénombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines 62 (1978), 61–80.

[2] O. Cogis, On the Ferrers dimension of a digraph, Discrete Math. 38 (1982), 47–52.

[3] L. Destrée, Problèmes algorithmiques sur les biordres et modèles relationnels apparentés, Master’s thesis, Université Libre de Bruxelles, Département d’Informatique, Brussels, Belgium, 1996.

[4] J.-P. Doignon, A. Ducamp, and J.-Cl. Falmagne, On realizable biorders and the biorder dimension of a relation, J. Math. Psych. 28 (1984), 73–109.

[5] P.C. Fishburn, Interval Orders and Interval Graphs, Wiley, 1985.

[6] R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, Addison Wesley, 1986.

[7] L. Guttman, A basis for scaling quantitative data, American Sociological Review 9 (1944), 139–150.

[8] P.E. Haxell, J.J. McDonald, and S.K. Thomason, Counting interval orders, Order 4 (1987), 269–272.

[9] B. Monjardet, Axiomatiques et propriétés des quasi-ordres, Math. Sci. Humaines 63 (1978), 51–82.

[10] J. Riguet, Les relations de Ferrers, C. R. Acad. Sci. Paris 232 (1951), 1729–1730.

[11] N.J.A. Sloane, The On-line Encyclopedia of Integer Sequences, Published electronically at http://www.research.att.com/∼njas/sequences/, 2003.

[12] M. Yannakakis, The complexity of the partial order dimension problem, SIAM J. Algebraic Discrete Methods 3 (1982), 351–358.

2000 Mathematics Subject Classification: Primary 05A15 ; Secondary 06A06. Keywords: biorder, Stirling number of the second kind.

(Concerned with sequence \underline{A006531}, \underline{A000108}, \underline{A022493}.)

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

Return to Journal of Integer Sequences home page.