The number of transitive relation containing exactly three ordered pairs

combinatoricsorder-theoryrelations

On a set $A=\{1,2,3,\cdots,n\}$ , what is the number of transitive relations, $t_{n,3}$ that contain exactly $3$ ordered pairs?

An example is the relation $\{(1,2),(2,3),(1,3)\}$

I calculated the same for some values of $n$ and the same are tabulated under:

\begin{array}{|c|c|}
\hline
\color{red}n&\color{red}{t_{n,3}}\\
\hline
0&0\\
\hline
1&0\\
\hline
2&2\\
\hline
3&43\\
\hline
4&276\\
\hline
\end{array}

What would be a general formula for $t_{n,3}$?

Best Answer

The formula is: $$t_{n,3} =2{n \choose 2} + 37{n \choose 3} + 116 {n \choose 4} + 180 {n \choose 5} + 120 {n \choose 6}$$

The general idea is to define $t_{n,3} = \sum_{k}d_{3,k}{n \choose k}$ where $d_{3,k}$ is the number of possible transitive relations in a set of size $k$ with exactly $3$ ordered pairs, that involve every element (ie. every element must appear in at least one pair). Then we generalize for a set of more than $k$ elements by doing a binomial of the subset of elements that do appear in pairs over the rest.

We have $3$ relations, involving no more than $6$ distinct elements, and the magic $d_{3,k}$ constants can be manually computed using a program. (tough it would be more elegant to find a solution that works without the aid of a computer).

Edit: here is the code I used to generate $d_{3,k}$ :

TransitiveMerge[{a_, b_}, {b_, c_}] := {{a, c}}
TransitiveMerge[{b_, c_}, {a_, b_}] := {{a, c}}
TransitiveMerge[x_, y_] := {}

TransitiveClosure[a_] := 
 DeleteDuplicates[
  Sort[Join[a, 
    Catenate[Map[TransitiveMerge[#[[1]], #[[2]]] &, Tuples[{a, a}]]]]]]

AllGraphs[n_, k_] := Subsets[Tuples[{Range[1, n], Range[1, n]}], {k}]

d[n_, k_] :=  
 d[n, k] = 
  Length[Select[
    AllGraphs[n, 
     k], (TransitiveClosure[#] === #) && 
      Length[DeleteDuplicates[Catenate[#]]] === n &]]

Comb[n_, k_] := Binomial[n, k] /; (NumberQ[n] && NumberQ[k])

t[n_, k_] := Apply[Plus, Map[Comb[n, #]* d[#, k] &, Range[1, 2*k]]]

t[n, 3]
t[n, 2]
Related Question