What is the number of transitive relation containing exactly three ordered pairs?

Question

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}$?

Answer 1

The number $t_{n,3}$ of relations is $$t_{n,3}=\sum_{k=2}^ 6 {n \choose k} t_{k,3}$$ as we already know. So we want to calculate $t_{n,3}, k=2,\ldots,6$. $t_{n,3}$ is the number of transitive relations on a set with $k$ elements, e.g. $\{0,1,\ldots,k-1\}$. If we have such a relation, e.g. $$\{(0, 0), (0, 1), (0, 2)\}$$ for n=3, we can generate other relations with the same property by renaming the elements and/or interchanging the coordinates of such a tuple. So if we change the first and the second number of this tuple we get the relation $$\{(0,0), (1,0), (2,0)\}$$ , if we rename $0$ to $1$, $1$ to $2$, $2$ to $0$, we get the relation $$\{(1,1), (1,2), (1,0)\}$$ which can be rewritten as $$\{1,0), (1,1), (1,2)\}$$ So the set of such relations of $n$ elements can be partitioned in classes of related relations, and from one the one class element the other class elements can be generated by renaming the numbers, or interchanging the coordinates. The following table shows the a relation for each class of relations for each number $n$ elements and the the size of the class, this is the number of differnt relations that can be generated by renameing and interchanging form the given relation. "sum" is the number of different relations of a set of $n$ different numbers.

N: number of different
   relations of this type

number of elements = 2      N
((0, 0), (0, 1), (1, 1))    2
sum =                       2

number of elements = 3      N
((0, 0), (0, 1), (0, 2))    6
((0, 0), (0, 1), (2, 1))   12
((0, 0), (0, 1), (2, 2))   12
((0, 0), (1, 1), (2, 2))    1
((0, 1), (0, 2), (1, 2))    6
sum =                      37

number of elements = 4      N
((0, 0), (0, 1), (2, 3))   48
((0, 0), (1, 1), (2, 3))   12
((0, 0), (1, 2), (1, 3))   24
((0, 1), (0, 2), (0, 3))    8
((0, 1), (0, 2), (3, 1))   24
sum =                     116

number of elements = 5      N
((0, 0), (1, 2), (3, 4))   60
((0, 1), (0, 2), (3, 4))  120
sum =                     180

number of elements = 6      N
((0, 1), (2, 3), (4, 5))  120
sum =                     120

So finally we get $$t_{n,3}=\frac{\left( n-1\right) n\, \left( {{n}^{4}}-5 {{n}^{3}}+19 {{n}^{2}}-28 n+10\right)}6,\; \forall n\ge6$$

Answer 2

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]