Counting structures of preference
A set $A$ of $n$ alternatives has $n!$ distinct linear orderings but only
$1$ type of linear ordering. This illustrates two possible viewpoints for
counting specific relations on $A$: either we see $A$ as a labelled set,
or we consider relations up to isomorphism. We first briefly review some
known results and open questions about counting specific preference structures
on $A$, such as weak orders, semiorders, or interval orders. Then we present
new findings about biorders (also called Guttman scales or Ferrers relations)
from a set $X$ of $m$ elements to a set $Y$ of $n$ elements. Counting biorders
up to isomorphism is easily done. For labelled sets $X$ and $Y$, a recurrence
formula as well as two explicit formulas involving Stirling numbers of the
second kind are obtained for the number of biorders from $X$ to $Y$. These
findings are taken from joint work with Julie Christophe and Samuel Fiorini
(a paper is accepted in the Journal of Integer Sequences).