\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{graphicx} \usepackage{amscd} \usepackage{amsfonts,amssymb,latexsym,enumerate,theorem} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \long\global\def\C#1\F{{}} \C---------------------------------- Revised version: October 22, 2003. ----------------------------------\F \C +++ MACROS +++ \F \newcommand{\one}{\textrm{1\hspace{-.5ex}l}} \newcommand{\BBB}{\mathcal{B}{}} \newcommand{\SSS}{\mathcal{S}{}} \newcommand{\WWW}{\mathcal{W}{}} \newcommand{\QED}{\mbox{}\nolinebreak\hfill\rule{2mm}{2mm}\medbreak\par} \C +++ THEOREM(S) DEFINITIONS +++ \F \theoremstyle{plain} \theoremheaderfont{\normalfont\bfseries} {\theorembodyfont{\normalfont\slshape} \newtheorem{theorem}{Theorem}%[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma}} {\theorembodyfont{\normalfont} \newtheorem{example}[theorem]{Example}} \C +++========================+++ \F \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Counting Biorders } \vskip 1cm \large Julie Christophe\footnote{J.~C. is a Fellow of the Fonds pour la Formation \`a la Recherche dans l'Industrie et dans l'Agriculture.}, Jean-Paul Doignon\footnote{Corresponding author.}, and Samuel Fiorini\footnote{S.~F. is supported by a Fellowship of the Belgian American Educational Foundation.} \\ Universit\'e Libre de Bruxelles\\ D\'epartement de Math\'ematique, c.p.~216\\ Bd du Triomphe\\ B-1050 Bruxelles\\ Belgium\\ \href{mailto:juchrist@ulb.ac.be}{\tt juchrist@ulb.ac.be} \\ \href{mailto:doignon@ulb.ac.be}{\tt doignon@ulb.ac.be} \\ \href{mailto:sfiorini@ulb.ac.be}{\tt sfiorini@ulb.ac.be} \\ \end{center} \vskip .2 in \begin{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. \end{abstract} \C==========================\F \section{Introduction} \label{Introduction} Throughout the text, $X$ and $Y$ denote finite sets of respective cardinalities $m$ and $n$. A \emph{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$, \dots, $x_m$ of the elements in $X$ and some ordering $y_1$, $y_2$, \dots, $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: \newcommand{\hor}{\rule [1mm]{3mm}{0.2mm}} \newcommand{\ver}{\rule [0mm]{0.2mm}{3mm}} \begin{eqnarray} \begin{array}{rcccccccccccccc} && y_1 && y_2 && y_3 && y_4 && y_5 && y_6 && y_7\\[4mm] x_1\quad &\ver& 1 && 1 && 1 && 1 && 1 && 1 && 1\\\\ x_2 \quad&\ver& 1 && 1 && 1 && 1 && 1 && 1 && 1\\ &&\hor&&\hor\\ x_3\quad && 0 && 0 & \ver & 1 && 1 && 1 && 1 && 1\\ &&&&&&\hor\\ x_4\quad && 0 && 0 && 0 &\ver& 1 && 1 && 1 && 1 \\ \\ x_5\quad && 0 && 0 && 0 &\ver& 1 && 1 && 1 && 1\\ &&&&&&&&\hor&&\hor&&\hor&&\hor \end{array} \end{eqnarray} Also, a relation $R$ from $X$ to $Y$ is a biorder if and only if it satisfies any of the following equivalent conditions: \begin{enumerate} \item for all $w,x\in X$ and $y,z\in Y$: \begin{eqnarray} (wRy\textrm{ and } xRz) &\textrm{ implies }& (wRz \textrm{ or } xRy); \end{eqnarray} \item all subsets $R(x)=\{y\in Y \,\vert\, xRy\}$, for $x\in X$, form a chain of subsets of $Y$ (repetitions being allowed); \item all subsets $R^{-1}(y)=\{x\in X \,\vert\, xRy\}$, for $y\in Y$, form a chain of subsets of $X$; \item no tableau for $R$ contains a subtableau of the form \begin{eqnarray} \left(\begin{array}{cc} 0 & 1\\ 1 & 0 \end{array} \right) \qquad\mathrm{or}\qquad \left(\begin{array}{cc} 1 & 0\\ 0 & 1 \end{array} \right). \end{eqnarray} \end{enumerate} These simple conditions, and several other ones, were established when biorders were first introduced in psychology as `scales' by Guttman \cite{Guttman44}, and then in mathematics as `Ferrers relations' by Riguet \cite{Riguet51}. For a survey of the early history of biorders, see Monjardet \cite{Monjardet1978}. 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 \cite{Yannakakis1982}, or they are used as the $1$-dimensional constituents in a dimensional theory of relations by Cogis \cite{Cogis1982b} and Doignon, Ducamp and Falmagne~\cite{DoignonDucampFalmagne84} (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 \cite{Fishburn1985} 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\in Z$ \begin{eqnarray} \label{eq-so} (xRy\textrm{ and } yRz) &\textrm{ implies }& (xRt \textrm{ or } tRz). \end{eqnarray} Formulas for the number of semiorders on an $n$-element set are given in Chandon, Lemaire and Pouget \cite{ChandonLemairePouget1978} (see also Sequence A006531 in the On-Line Encyclopedia of Integer Sequences~\cite{SloaneEIS}), 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 $\frac1{n+1}{2n \choose n}$ (see \cite{Fishburn1985} or Sequence A000108~\cite{SloaneEIS}), while a polynomial-time algorithm for computing the number of isomorphism types of interval orders is due to Haxell, McDonald and Thomason~\cite{HaxellMcDonaldThomason1987} (Sequence A022493~\cite{SloaneEIS}). On the other hand, the case of biorders from $X$ to $Y$ is easy in case $X \cap Y =\varnothing$: there are ${m+n\choose n}$ isomorphism types of biorders from an $m$-element set $X$ to a disjoint $n$-element 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. \C===============================================================\F \section{Double Recurrence} \label{Double Recurrence} Let us denote by $\BBB(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 \cap Y=\varnothing$ does not set any restriction here, because of the duplication construction of Doignon, Ducamp and Falmagne~\cite{DoignonDucampFalmagne84}; the reader might find it helpful to assume $X\cap Y=\varnothing$. The following proposition shows how to compute numbers $\BBB(m,n)$ by a double recurrence. \begin{proposition} \label{dr} For $m>0$ and $n>0$, we have \begin{eqnarray} \label{eqdr} \BBB(m,n) &=& \sum_{j=0}^{m-1} \;\sum_{k=0}^{n-1} \;\;{m \choose j} \; {n \choose k} \; \BBB(j,k) \end{eqnarray} and \begin{eqnarray} \label{eqdr0} \BBB(m,0) \;=\; \BBB(0,n) \;=\; 1, \end{eqnarray} together with \begin{eqnarray} \label{eqdr00} \BBB(0,0) &=& 2. \end{eqnarray} \end{proposition} \noindent\emph{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\in Y$; denote by $\BBB_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 $\BBB_1(m,n)$ the number of such biorders. Notice the equality \begin{eqnarray} \label{0t1} \BBB_0(m,n) &=& \BBB_1(n,m), \end{eqnarray} 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 \begin{eqnarray} \label{0-1} \BBB(m,n) &=& \BBB_0(m,n) + \BBB_1(m,n). \end{eqnarray} To obtain recurrence relations first for $\BBB_1(m,n)$ and then for $\BBB(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 \le 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 \begin{equation} \label{1-1} \BBB_1(m,n) \;=\; \sum_{j=0}^{m-1} \;\;\;{m \choose j} \; \BBB_0(j,n) \;=\; \sum_{j=0}^{m-1} \;\;\;{m \choose j} \; \BBB_1(n,j). \end{equation} Now the following computations based on Equations~(\ref{0t1})--(\ref{1-1}) give us Equation~(\ref{eqdr}) in the statement: \begin{eqnarray*} \BBB(m,n) &=& \BBB_0(m,n) + \BBB_1(m,n)\\ &=& \BBB_1(n,m) + \BBB_1(m,n)\\ % &=&\sum_{k=0}^{n-1} \;\;\;{n \choose k} \; \BBB_1(m,k) + \sum_{j=0}^{m-1} \;\;\;{m \choose j} \; \BBB_1(n,j)\\ % &=&\sum_{k=0}^{n-1} {n \choose k} \sum_{j=0}^{m-1} {m \choose j} \BBB_0(j,k) + \sum_{j=0}^{m-1} {m \choose j} \sum_{k=0}^{n-1} {n \choose k} \BBB_1(j,k)\\ % &=& \sum_{j=0}^{m-1}\; \sum_{k=0}^{n-1} \;\;\; {m \choose j} \; {n \choose k} \; \BBB(j,k). \end{eqnarray*} Finally, the values in Equations~(\ref{eqdr0})--(\ref{eqdr00}) are chosen to generate the correct expressions $\BBB(m,1)=2^m$ and $\BBB(1,n)=2^n$. \QED With a program implementing the formulas from Equation~(\ref{eqdr}), we computed the values of $\BBB(m,n)$ shown in Table~1. Notice $\BBB(m,n)=\BBB(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 $\BBB(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 $\BBB(2,n)= 2\cdot 3^n - 2 ^n$. \begin{table} \begin{center} \halign{ $#$\quad&&\quad\hfil$#$\cr m \backslash n&1&2&3&4&5&6&7&8\cr \noalign{\vskip3mm\hrule\vskip3mm} 1&2&4&8&16&32&64&128&256\cr 2&&14&46&146&454&1\,394&4\,246&12\,866\cr 3&&&230&1\,066&4\,718&20\,266&85\,310&354\,106\cr 4&&&&6\,902&41\,506&237\,686&1\,315\,666& 7\,107\,302\cr 5&&&&&329\,462&2\,441\,314&17\,234\,438&117\,437\,746\cr 6&&&&&&22\,934\,773& 202\,229\,266& 1\,701\,740\,006\cr} \end{center} \caption{Some values of $\BBB(m,n)$.} \end{table} \C=================================================================\F \section{A First Explicit Formula} \label{First Explicit} Some hand computations exploiting the double-recurrence in Proposition~\ref{eqdr} strongly suggest to write $\BBB(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 $\SSS(m,j)$ (see, e.g., \cite{GrahamKnuthPatashnik1989} where the notation $\left\{m \atop j \right\}$ is used). Remember that $\SSS(m,j)$, the number of ways of partitioning an $m$-element set into $j$ classes, equals \begin{eqnarray} \label{eqst} \SSS(m,j) &=& \frac{1}{j!}\;\sum_{i=1}^j (-1)^{j-i} \; {j \choose i} \; i^m. \end{eqnarray} Here are some other properties of these numbers, for $m>0$: \begin{eqnarray} \SSS(m,j)&=&0 \qquad\mathrm{when~} j < 1 \mathrm{~or~} m < j,\\ \SSS(m,m)&=&\SSS(m,1)\;=\;1, \end{eqnarray} and \begin{eqnarray} \label{eqStrec} \SSS(m,u) &=& \SSS(m-1,u-1)+u\; \SSS(m-1,u). \end{eqnarray} We will also need (see \cite{GrahamKnuthPatashnik1989}, Equation~(6.17) and on page 264, the formula for $x^n$, with $x$ set to $1$): for $1 \le j \le m$, \begin{eqnarray} \label{eqSt} \SSS(m,j) &=& \sum_{k=j}^m\;\;{m \choose k} \; (-1)^{m-k} \; \SSS(k+1,j+1), \end{eqnarray} and for $m \ge 1$, \begin{eqnarray} 1&=&\sum_{t=1}^{m} \;\; (-1)^{m+t} \; t! \; \SSS(m,t) \label{eqnew}. \end{eqnarray} \begin{proposition} \label{fe} For $m>0$ and $n\ge 0$, we have \begin{eqnarray} \label{eqfe} \BBB(m,n) &=& \sum_{t=1}^{m}\;\; (-1)^{m+t}\; t! \; \SSS(m,t) \; (t+1)^n. \end{eqnarray} \end{proposition} \noindent\emph{Proof}. Setting for $m>0$ and $m \ge t \ge 1$ \begin{eqnarray} \label{eqb} b_{m,t} &=& (-1)^{m+t}\; t! \; \SSS(m,t), \end{eqnarray} and also for convenience $b_{m,m+1}=0$, we first record some properties of the numbers $b_{m,n}$: \begin{eqnarray} b_{m,1} &=& (-1)^{m+1};\label{eqA}\\ b_{m,m} &=& m!\;;\label{eqB}\\ b_{m,t} &=& \sum_{j=t-1}^{m-1} \;\; {m \choose j} (b_{j,t-1}-b_{j,t}), \qquad \mathrm{for~} 1 < t < m\label{eqC}. \end{eqnarray} Equation~(\ref{eqA}) follows from $\SSS(m,1)=1$, and Equation~(\ref{eqB}) from $\SSS(m,m)=1$. More computations are needed for the next equation. Starting from the right-hand side of Equation~(\ref{eqC}), we have (in view of Equations~(\ref{eqStrec}) and (\ref{eqSt})) \begin{eqnarray*} \lefteqn{\sum_{j=t-1}^{m-1} \;\; {m \choose j} (b_{j,t-1}-b_{j,t})}\hspace{9mm}\\ &=&\sum_{j=t-1}^{m-1} \;\; {m \choose j} (-1)^{j+t-1} (t-1)! \; \Big(\SSS(j,t-1)+t \; \SSS(j,t)\Big)\\ &=& (t-1)! \; (-1)^{t-1} \; \sum_{j=t-1}^{m-1}\;\; {m \choose j} \; (-1)^j \; \SSS(j+1,t)\\ &=& (t-1)! \; (-1)^{t-1} \; (-1)^m \; \big(\SSS(m,t-1)-\SSS(m+1,t)\big)\\ &=& (-1)^{m+t} \; (t-1)! \; t \; \SSS(m,t)\\ &=& b_{m,t} \end{eqnarray*} which establishes Equation~(\ref{eqC}). Next we establish by double recurrence on $m>0$ and $n\ge 0$ the equality in the thesis, rephrased as: \begin{eqnarray} \label{eqbb} \BBB(m,n) &=& \sum_{t=1}^{m} b_{m,t}\; (t+1)^n. \end{eqnarray} This equality holds for sure in case $m=1$ because of $\BBB(1,n)=2^n$ and Equation~(\ref{eqA}); it also holds in case $n=0$, in view of $\BBB(m,0)=1$ for $m\neq 0$ and Equation~(\ref{eqnew}). Supposing now that the following equation holds for $1 \le j < m$ and $0\le k < n$ \begin{eqnarray} \label{eqind} \BBB(j,k) &=& \sum_{t=1}^{j} b_{j,t}\; (t+1)^k, \end{eqnarray} we proceed to infer Equation~(\ref{eqbb}). After having inserted Equation~(\ref{eqind}) into Equation~(\ref{eqdr}), we get successively \begin{eqnarray*} \lefteqn{\BBB(m,n) } \hspace{3mm}\\ &=&\sum_{j=0}^{m-1} \;\sum_{k=0}^{n-1} \;\;{m \choose j} \; {n \choose k} \; \BBB(j,k)\\ % &=& \BBB(0,0) + \sum_{k=1}^{n-1} \; {n \choose k} \; \BBB(0,k) + \sum_{j=1}^{m-1} \sum_{k=0}^{n-1} {m \choose j} \; {n \choose k} \; \sum_{t=1}^{j} \;b_{j,t}\; (t+1)^k\\ % &=& 2 + (2^n-2) + \sum_{j=1}^{m-1} \; {m \choose j} \; \sum_{t=1}^{j} \; b_{j,t} \; \sum_{k=0}^{n-1} \; {n \choose k} \; (t+1)^k\\ &=& 2^n + \sum_{j=1}^{m-1} \; {m \choose j} \sum_{t=1}^{j} \; b_{j,t} (1+t+1)^n - \sum_{j=1}^{m-1} {m \choose j} \sum_{t=1}^{j}\; b_{j,t} (t+1)^n. \end{eqnarray*} Then replacing $t+1$ with $t$ in the second term, we have \begin{eqnarray*} \lefteqn{\BBB(m,n) }\hspace{1mm}\\ &=& 2^n + \sum_{j=1}^{m-1} \; {m \choose j} \; \sum_{t=2}^{j+1} \; b_{j,t-1} \; (t+1)^n - \sum_{j=1}^{m-1} \; {m \choose j} \; \sum_{t=1}^{j} \;\; b_{j,t} (t+1)^n\\ % % % &=&\left(1-\sum_{j=1}^{m-1} {m \choose j}\; b_{j,1} \right) 2^n + \sum_{j=1}^{m-1} \; {m \choose j} \; \sum_{t=2}^{j+1} \; \left(b_{j,t-1}-b_{j,t}\right) \; (t+1)^n \end{eqnarray*} and using $b_{j,j+1}=0$ \begin{eqnarray*} \lefteqn{\BBB(m,n) }\hspace{1mm}\\ % % &=&\left(1-\sum_{j=1}^{m-1} {m \choose j}\; (-1)^{j+1} \right) 2^n + \sum_{t=2}^{m} \; (t+1)^n\; \sum_{j=t-1}^{m-1} \;\; {m \choose j} \; \left( b_{j,t-1}-b_{j,t}\right)\\ % % % &=&(-1)^{m+1}\; 2^n\\ &&\qquad\qquad + \sum_{t=2}^{m-1} \; (t+1)^n\; \sum_{j=t-1}^{m-1} \;\; {m \choose j} \; \left( b_{j,t-1}-b_{j,t}\right) \\&&\qquad\qquad\qquad\qquad + m\; b_{m-1,m-1} \; (m+1)^n.\end{eqnarray*} Now Equations~(\ref{eqA}), (\ref{eqC}), (\ref{eqB}) lead to \begin{eqnarray*} \BBB(m,n) &=& b_{m,1} 2^n + \sum_{t=2}^{m-1} \;\; b_{m,t} \; (t+1)^n + b_{m,m}\; (m+1)^n \end{eqnarray*} which is Equation~(\ref{eqbb}). This completes the proof by recurrence. \QED Replacing the Stirling numbers in Equation~(\ref{eqfe}) with their expressions from Equation~(\ref{eqst}), we derive the more explicit formula \begin{eqnarray} \BBB(m,n) &=& \sum_{i=1}^{m}\; (-1)^{m-i}\;\; i^m \; \sum_{t=i}^m \; {t \choose i} \; (t+1)^n. \end{eqnarray} Another reformulation is obtained by introducing the number $\WWW(m,k)=k!\;\SSS(m,k)$ of weak orders with $k$ classes on an $m$-element set: \begin{eqnarray} \BBB(m,n) &=& \sum_{t=1}^{m}\;\; (-1)^{m+t}\; \WWW(m,t) \; (t+1)^n. \end{eqnarray} All of these formulas for $\BBB(m,n)$ are alternating sums. We now turn to another way of counting, which will provide us with a sum of positive terms. \C===============================================================\F \section{A Second Explicit Formula} \label{Second Explicit} 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 \begin{eqnarray} x \;B_X\; x' \iff B(x) \subseteq B(x'), \quad\mathrm{ and }\quad y \;B_Y\; y' \iff B^{-1}(y) \subseteq B^{-1}(y'). \end{eqnarray} \begin{proposition} \label{prop-sf} 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$. \end{proposition} \noindent\emph{Proof}. All assertions can be easily checked by considering a step-like tableau for the (given or to-be-constructed) biorder $B$. \QED 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\'ee \cite{Destree1996}. \begin{proposition} \label{prop-sfbis} The number $\BBB(m,n)$ of biorders from $X$ to $Y$, where $|X|=m$ and $|Y|=n$, equals \begin{eqnarray} \BBB(m,n) &=& \sum_{k=1}^m k!\; (k-1)! \; \SSS(m,k) \; \big(\SSS(n+1,k) + k\, \SSS(n+1,k+1)\big).\label{eq-sf} \end{eqnarray} \end{proposition} Remark that, contrary to Equation~(\ref{eqfe}), we have here a sum of positive terms. On the other hand, there are more summations here, because each Stirling number requires one. \vspace{2mm} \noindent\emph{Proof}. >From Proposition~\ref{prop-sf}, we derive \begin{eqnarray*} \lefteqn{\BBB(m,n) \quad=}\\ &&\sum_{k=1}^m k!\, \SSS(m,k) \, \big( (k-1)! \, \SSS(n,k-1) + 2 \, k!\, \SSS(n,k) + (k+1)!\, \SSS(n,k+1)\big). \end{eqnarray*} Applying Equation~(\ref{eqStrec}), we get Equation~(\ref{eq-sf}). \QED In the particular case $m=n$, we have \cite{Destree1996} \begin{eqnarray} \BBB(m,m) &=& 2\;\sum_{k=1}^m \; (k!)^2\; \SSS(m,k) \; \SSS(m+1,k+1). \end{eqnarray} Returning to the general case, we conclude that the number of biorders both equals either side of \begin{eqnarray} \lefteqn{ \sum_{t=1}^{m}\;\; (-1)^{m+t}\; t! \; \SSS(m,t) \; (t+1)^n \quad=}\nonumber\\ &&\sum_{k=1}^m k!\; (k-1)! \; \SSS(m,k) \; \big(\SSS(n+1,k) + k\, \SSS(n+1,k+1)\big) \label{eqf} \end{eqnarray} and is the solution to the double recurrence, for $m>0$ and $n>0$, \begin{eqnarray} \BBB(m,n) &=& \sum_{j=0}^{m-1} \;\sum_{k=0}^{n-1} \;\;{m \choose j} \; {n \choose k} \; \BBB(j,k), \label{eqff} \end{eqnarray} with initial conditions \begin{eqnarray} \BBB(m,0) = \BBB(0,n) = 1 &\mathrm{and}& \BBB(0,0) = 2. \end{eqnarray} \C===============================\F %\bibliographystyle{plain} %\bibliography{jpd} \begin{thebibliography}{10} \bibitem{ChandonLemairePouget1978} J.-L.~Chandon, J.~Lemaire, and J.~Pouget, \newblock D\'enombrement des quasi-ordres sur un ensemble fini, \newblock {\em Math.\ Sci.\ Humaines} {\bf 62} (1978), 61--80. \bibitem{Cogis1982b} O.~Cogis, \newblock On the {F}errers dimension of a digraph, \newblock {\em Discrete Math.} {\bf 38} (1982), 47--52. \bibitem{Destree1996} L.~{Destr{\'e}e}, \newblock Probl{\`e}mes algorithmiques sur les biordres et mod{\`e}les relationnels apparent{\'e}s, \newblock Master's thesis, Universit{\'e} Libre de Bruxelles, D{\'e}partement d'Informatique, Brussels, Belgium, 1996. \bibitem{DoignonDucampFalmagne84} J.-P.~Doignon, A.~Ducamp, and J.-Cl.~Falmagne, \newblock On realizable biorders and the biorder dimension of a relation, \newblock {\em J.\ Math.\ Psych.} {\bf 28} (1984), 73--109. \bibitem{Fishburn1985} P.C.~Fishburn, \newblock {\em Interval Orders and Interval Graphs}, \newblock Wiley, 1985. \bibitem{GrahamKnuthPatashnik1989} R.L.~Graham, D.E.~Knuth, and O.~Patashnik, \newblock {\em Concrete Mathematics}, \newblock Addison Wesley, 1986. \bibitem{Guttman44} L.~Guttman, \newblock A basis for scaling quantitative data, \newblock {\em American Sociological Review} {\bf 9} (1944), 139--150. \bibitem{HaxellMcDonaldThomason1987} P.E.~Haxell, J.J.~McDonald, and S.K.~Thomason, \newblock Counting interval orders, \newblock {\em Order} {\bf 4} (1987), 269--272. \bibitem{Monjardet1978} B.~Monjardet, \newblock Axiomatiques et propri\'et\'es des quasi-ordres, \newblock {\em Math.\ Sci.\ Humaines} {\bf 63} (1978), 51--82. \bibitem{Riguet51} J.~Riguet, \newblock Les relations de {F}errers, \newblock {\em C.\ R.\ Acad.\ Sci.\ Paris} {\bf 232} (1951), 1729--1730. \bibitem{SloaneEIS} N.J.A.~Sloane, \newblock {\em The On-line Encyclopedia of Integer Sequences}, \newblock {P}ublished electronically at http://www.research.att.com/$\sim$njas/sequences/, 2003. \bibitem{Yannakakis1982} M.~Yannakakis, \newblock The complexity of the partial order dimension problem, \newblock {\em SIAM J.\ Algebraic Discrete Methods} {\bf 3} (1982), 351--358. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15 ; Secondary 06A06. \noindent \emph{Keywords: } biorder, Stirling number of the second kind. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A006531}, \seqnum{A000108}, \seqnum{A022493}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received February 17 2003; revised version received October 27 2003. Published in {\it Journal of Integer Sequences}, December 12 2003. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip .1in \end{document}