1 Introduction

Let S be a non-empty set. Any subset of \(S\times S\) is a relation on S. A relation on S is transitive if and only if \(\forall x,y,z\in S\), \((x,y)\in S\) \(\wedge\) \((y,z)\in S\) \(\Rightarrow (x,z)\in S\).

OEIS [1] enlists the the number of transitive relations on sets with less than 19 elements. An explicit formula, if any, for the number of transitive relations on a set with n elements is still undiscovered.

Let t(n) denote the number of transitive relations on a set with n elements. OEIS [1] enumerates \(t(n), \forall n<19\). The number of transitive relations on a set, t(n), with \(n<19\) is tabulated as follows:

n

No. of transitive relations, t(n)

0

1

1

2

2

13

3

171

4

3994

5

154303

6

9415189

7

878222530

8

122207703623

9

24890747921947

10

7307450299510288

11

3053521546333103057

12

1797003559223770324237

13

1476062693867019126073312

14

1679239558149570229156802997

15

2628225174143857306623695576671

16

5626175867513779058707006016592954

17

16388270713364863943791979866838296851

18

64662720846908542794678859718227127212465

2 Main Discussion

We prove that a formula, if any, for the number of transitive relations on a set cannot be a polynomial.

Theorem 1

\(\not \exists p(n)=\sum \limits _{\begin{array}{c} r \end{array}=0}^{m}a_rn^r\), \(a_i\in {\mathbb {Z}}\) such that, \(p(n)= t(n), \forall n\in {\mathbb {N}}\).

Proof

Let \(p(n)=\sum \limits _{\begin{array}{c} r \end{array}=0}^{m}a_rn^r\) be a polynomial in n.

If possible, let \(p(n)= t(n), \forall n\in {\mathbb {N}}\).

Since \(t(0)=1, t(3)=171\), we have

\(t(0)=p(0)=\sum \limits _{\begin{array}{c} r \end{array}=0}^m a_r0^r=1\)\(\Rightarrow a_0=1\)

$$\begin{aligned} a_0=1 \end{aligned}$$
(1)

\(t(3)=p(3)=\sum \limits _{\begin{array}{c} r \end{array}=0}^m a_r3^r=171\Rightarrow a_0+3a_1+3^2a_2+3^3a_3+...+3^ma_m=171\Rightarrow 3a_1+3^2a_2+3^3a_3+...+3^ma_m=170\)       (from (1))

$$\begin{aligned} a_1+3a_2+3^2a_3+...+3^{m-1}a_m=\frac{170}{3} \end{aligned}$$
(2)

The proof is a direct consequence of (2). Since the sum of a finite number of integer terms cannot be a fraction, we conclude that at least one of \(a_i, i\in {\{1,2,3,...,m}\}\) is not an integer.

Thus, \(\not \exists p(n)=\sum \limits _{\begin{array}{c} r \end{array}=0}^{m}a_rn^r\), \(a_i\in {\mathbb {Z}}\) such that, \(p(n)= t(n), \forall n\in {\mathbb {N}}\). □

We now state and prove a simple, but powerful inequality regarding t(n), the number of transitive relations on a set.

Theorem 2

Let \(n,n_1,n_2\in {\mathbb {N}}\).

$$\begin{aligned} n=n_1+n_2\Rightarrow t(n)> t(n_1)t(n_2). \end{aligned}$$
(3)

Proof

Consider the set \(A=\{a_1, a_2, a_3, ..., a_n\}\). We partition A into two sets \(A_1\) and \(A_2\), not necessarily non-empty, such that \(A=A_1\cup A_2\) and \(A_1\cap A_2=\phi\). Let \(|A_1|=n_1\) and \(|A|_2=n_2\). Since \(A_1\) contains \(n_1\) elements, there are \(t(n_1)\) transitive relations on \(A_1\). Similarly, there are \(t(n_2)\) transitive relations on \(A_2\). Now, if \(T_1\) and \(T_2\) are transitive relations on \(A_1\) and \(A_2\) respectively, then \(T_1\cup T_2\) is a transitive relation on A. Since there are \(t(n_1)\) transitive relations on \(A_1\) and \(t(n_2)\) transitive relations on \(A_2\), using the multiplication principle of counting, there are \(t(n_1)t(n_2)\) possibilities for \(T_1\cup T_2\). Consequently, there are at least \(t(n_1)t(n_2)\) transitive relations on A. □

2.1 Corollary 1

$$\begin{aligned} t(n)> 2\times t(n-1), \forall n{\mathbb {N}} \end{aligned}$$

Proof

In (3) , put \(n_1=1\) so that \(n_2=n-1\). We get

$$\begin{aligned}&t(n)> t(1) t(n-1)\\&t(n)>2\times t(n-1) \qquad \qquad (\because t(1)=2) \end{aligned}$$

□

2.2 Example:

$$\begin{aligned} t(4)=t(2+2)> t(2)t(2)=13\times 13=169\\ t(4)=t(1+3)> t(1)t(3)=2\times 171=342\\ \end{aligned}$$

The following theorem provides a larger lower bound for t(n).

Theorem 3

Let \(n,n_1,n_2\in {\mathbb {N}}\) such that \(n=n_1+n_2\). The following inequality holds:

$$\begin{aligned} t(n)> t(n_1)t(n_2)+(2^{n_1}-1)t(n_2)+(2^{n_2}-1)t(n_1) \end{aligned}$$
(4)

Proof

Consider the set \(A=\{a_1, a_2, a_3, ..., a_n\}\). As before, we partition A into two sets \(A_1=\{b_1, b_2, b_3, ..., b_{n_1}\}\) and \(A_2=\{c_1,c_2,c_3,...,c_{n_2}\}\), not necessarily non-empty, such that \(A=A_1\cup A_2\) and \(A_1\cap A_2=\phi\). From theorem 1, we get \(t(n)> t(n_1)t(n_2)\).

Now, for each \(b_\lambda \in A_1\), consider \(B_\lambda =\{(b_\lambda ,c_i), \forall i=1,2,3,...,n_2\}.\) If \(T_2\) is any transitive relation on \(A_2\), then \(B_\lambda \cup T_2\) is a transitive relation on A. Similarly, for each \(c_\mu \in A_2\), consider \(C_\mu =\{(b_i,c_\mu ), \forall i=1,2,3,...,n_1\}\). If \(T_1\) is any transitive relation on \(A_1\), then \(C_\mu \cup T_1\) is a transitive relation on A. Interestingly, if \(b_{\lambda _1}, b_{\lambda _2}\in A_1\) and \(B_{\lambda _1}\), \(B_{\lambda _2}\) are constructed the same way as that of \(B_\lambda\), we observe that if \(T_2\) is a transitive relation on \(A_2\), then \(B_{\lambda _1}\cup B_{\lambda _2}\cup T_2\) is a transitive relation on A. Similarly, if \(c_{\mu _1}, c_{\mu _2}\in A_2\) and \(C_{\mu _1}\), \(C_{\mu _2}\) are constructed the same way as that of \(C_\mu\), we observe that if \(T_1\) is a transitive relation on \(A_1\), then \(C_{\mu _1}\cup C_{\mu _2}\cup T_1\) is a transitive relation on A. The same argument can be successfully continued to any number of elements \(b_{\lambda _1}, b_{\lambda _2}, ..., b_{\lambda _r}\in A_1, r\le n_1\) and \(c_{\mu _1}, c_{\mu _2}, ..., c_{\mu _s}\in A_2, s\le n_2\).

Consequently,

$$\begin{aligned} t(n)> t(n_1)t(n_2)&+\left( {\begin{array}{c}n_1\\ 1\end{array}}\right) t(n_2)+\left( {\begin{array}{c}n_1\\ 2\end{array}}\right) t(n_2)+...+\left( {\begin{array}{c}n_1\\ n_1\end{array}}\right) t(n_2)\\&+\left( {\begin{array}{c}n_2\\ 1\end{array}}\right) t(n_1)+\left( {\begin{array}{c}n_2\\ 2\end{array}}\right) t(n_1)+...+\left( {\begin{array}{c}n_2\\ n_2\end{array}}\right) t(n_1)\\ \end{aligned}$$
$$\begin{aligned} \Rightarrow t(n)> t(n_1)t(n_2)&+\bigg (\left( {\begin{array}{c}n_1\\ 1\end{array}}\right) +\left( {\begin{array}{c}n_1\\ 2\end{array}}\right) +...+\left( {\begin{array}{c}n_1\\ n_1\end{array}}\right) \bigg )t(n_2)\\&+\bigg (\left( {\begin{array}{c}n_2\\ 1\end{array}}\right) +\left( {\begin{array}{c}n_2\\ 2\end{array}}\right) +...+\left( {\begin{array}{c}n_2\\ n_2\end{array}}\right) \bigg )t(n_1) \end{aligned}$$

Using the fact that \(\left( {\begin{array}{c}n\\ 1\end{array}}\right) +\left( {\begin{array}{c}n\\ 2\end{array}}\right) +...+\left( {\begin{array}{c}n\\ n\end{array}}\right) =2^n-1\), we conclude that

$$\begin{aligned} t(n)> t(n_1)t(n_2)+\big (2^{n_1}-1\big )t(n_2)+\big (2^{n_2}-1\big )t(n_1) \end{aligned}$$

□

The following corollary gives a useful recursive relation for t(n).

2.3 Corollary 2

The following holds:

$$\begin{aligned} t(n)> 3\times t(n-1)+2^n-2, \forall n{\mathbb {N}} \end{aligned}$$

Proof

In (4), choose \(n_1=1\) so that \(n_2=n-1\). We get

$$\begin{aligned}&t(n)> t(1)t(n-1)+(2^1-1)t(n-1)+(2^{n-1}-1)t(n_1)\\&t(n)> 2\times t(n-1)+t(n-1)+(2^{n-1}-1)2\\&t(n)>3\times t(n-1)+2^n-2 \end{aligned}$$

□

An even larger lower bound for t(n) is obtained in (5) using the following result.

Theorem 4

Let \(n,n_1,n_2\in {\mathbb {N}}\) such that \(n=n_1+n_2\). The following inequality holds:

$$\begin{aligned} t(n)> t(n_1)t(n_2)+t(n_2)\bigg [\sum _{r=1}^{n_1}\left( {\begin{array}{c}n_1\\ r\end{array}}\right) t(n_1-r)\bigg ]+t(n_1)\bigg [\sum _{r=1}^{n_2}\left( {\begin{array}{c}n_2\\ r\end{array}}\right) t(n_2-r)\bigg ] \end{aligned}$$
(5)

Proof

Consider the set \(A=\{a_1, a_2, a_3, ..., a_n\}\). As before, we partition A into two sets \(A_1=\{b_1, b_2, b_3, ..., b_{n_1}\}\) and \(A_2=\{c_1,c_2,c_3,...,c_{n_2}\}\), not necessarily non-empty, such that \(A=A_1\cup A_2\) and \(A_1\cap A_2=\phi\). From theorem 1, we get \(t(n)> t(n_1)t(n_2)\). Now, for each \(b_\lambda \in A_1\), consider \(B_\lambda =\{(b_\lambda ,c_i), \forall i=1,2,3,...,n_2\}.\) If \(T_2\) is any transitive relation on \(A_2\) and T is any transitive relation on \(A_1- B_\lambda\), then \(B_\lambda \cup T_2\cup T\) is a transitive relation on A. Similarly, for each \(c_\mu \in A_2\), consider \(C_\mu =\{(b_i,c_\mu ), \forall i=1,2,3,...,n_1\}\). If \(T_1\) is any transitive relation on \(A_1\) and S is a transitive relation on \(A_2-C_\lambda\), then \(C_\mu \cup T_1\cup S\) is a transitive relation on A. Interestingly, if \(b_{\lambda _1}, b_{\lambda _2}\in A_1\) and \(B_{\lambda _1}\), \(B_{\lambda _2}\) are constructed the same way as that of \(B_\lambda\), we observe that if \(T_2\) is a transitive relation on \(A_2\) and T is a transitive relation on \(A_1-\{{B_{\lambda _1} ,B_{\lambda _2}\}}\) , then \(B_{\lambda _1}\cup B_{\lambda _2}\cup T_2\cup T\) is a transitive relation on A. Similarly, if \(c_{\mu _1}, c_{\mu _2}\in A_2\) and \(C_{\mu _1}\), \(C_{\mu _2}\) are constructed the same way as that of \(C_\mu\), we observe that if \(T_1\) is a transitive relation on \(A_1\) and S is a transitive relation on \(A_2-\{C_{\mu _1},C_{\mu _2}\}\), then \(C_{\mu _1}\cup C_{\mu _2}\cup T_1\cup S\) is a transitive relation on A. The same argument can be successfully continued to any number of elements \(b_{\lambda _1}, b_{\lambda _2}, ..., b_{\lambda _r}\in A_1, r\le n_1\) and \(c_{\mu _1}, c_{\mu _2}, ..., c_{\mu _s}\in A_2, s\le n_2\).

Consequently,

$$\begin{aligned} t(n)&> t(n_1)t(n_2)\\&+\left( {\begin{array}{c}n_1\\ 1\end{array}}\right) t(n_2)t(n_1-1)+\left( {\begin{array}{c}n_1\\ 2\end{array}}\right) t(n_2)t(n_1-2)+... +\left( {\begin{array}{c}n_1\\ n_1\end{array}}\right) t(n_2)t(0)\\&+\left( {\begin{array}{c}n_2\\ 1\end{array}}\right) t(n_1)t(n_2-1)+\left( {\begin{array}{c}n_2\\ 2\end{array}}\right) t(n_1)t(n_2-2) +...+\left( {\begin{array}{c}n_2\\ n_2\end{array}}\right) t(n_1)t(0) \end{aligned}$$

This gives

$$\begin{aligned} t(n)&> t(n_1)t(n_2)\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \\&+\bigg [\left( {\begin{array}{c}n_1\\ 1\end{array}}\right) t(n_1-1)+\left( {\begin{array}{c}n_1\\ 2\end{array}}\right) t(n_1-2)+... +\left( {\begin{array}{c}n_1\\ n_1\end{array}}\right) t(0)\bigg ]t(n_2)\\&+\bigg [\left( {\begin{array}{c}n_2\\ 1\end{array}}\right) t(n_2-1)+\left( {\begin{array}{c}n_2\\ 2\end{array}}\right) t(n_2-2)+...+\left( {\begin{array}{c}n_2\\ n_2\end{array}}\right) t(0)\bigg ]t(n_1) \end{aligned}$$

This simplifies to

$$\begin{aligned} t(n)> t(n_1)t(n_2)+t(n_2)\bigg [\sum _{r=1}^{n_1}\left( {\begin{array}{c}n_1\\ r\end{array}}\right) t(n_1-r)\bigg ]+t(n_1)\bigg [\sum _{r=1}^{n_2}\left( {\begin{array}{c}n_2\\ r\end{array}}\right) t(n_2-r)\bigg ] \end{aligned}$$

□

2.4 Corollary 3

The following holds:

$$\begin{aligned} t(n)> 3\times t(n-1)+2\bigg [\sum _{r=1}^{n-1}\left( {\begin{array}{c}n-1\\ r\end{array}}\right) t(n-1-r)\bigg ] \end{aligned}$$

Proof

In (5), choose \(n_1=1\) so that \(n_2=n-1\). We get

$$\begin{aligned}&t(n)> t(1)t(n-1)+t(n-1)\bigg [\sum _{r=1}^{1}\left( {\begin{array}{c}1\\ r\end{array}}\right) t(1-r)\bigg ]+t(1)\bigg [\sum _{r=1}^{n-1}\left( {\begin{array}{c}n-1\\ r\end{array}}\right) t(n-1-r)\bigg ]\\&t(n)> t(1)t(n-1)+t(n-1)t(0)+t(1)\bigg [\sum _{r=1}^{n-1}\left( {\begin{array}{c}n-1\\ r\end{array}}\right) t(n-1-r)\bigg ]\\&t(n)> 2\times t(n-1)+t(n-1)+2\bigg [\sum _{r=1}^{n-1}\left( {\begin{array}{c}n-1\\ r\end{array}}\right) t(n-1-r)\bigg ]\\&t(n)> 3\times t(n-1)+2\bigg [\sum _{r=1}^{n-1}\left( {\begin{array}{c}n-1\\ r\end{array}}\right) t(n-1-r)\bigg ]\\ \end{aligned}$$

□

2.4.1 Example:

$$\begin{aligned}&\qquad t(4)> 3\times t(3)+2\bigg [\sum _{r=1}^{3}\left( {\begin{array}{c}3\\ r\end{array}}\right) t(3-r)\bigg ]\\&\Rightarrow t(4)> 3\times t(3)+2\bigg [\left( {\begin{array}{c}3\\ 1\end{array}}\right) t(3-1)+\left( {\begin{array}{c}3\\ 2\end{array}}\right) t(3-2)+\left( {\begin{array}{c}3\\ 3\end{array}}\right) t(3-3)\bigg ]\\&\Rightarrow t(4)> 3\times t(3)+2\bigg [\left( {\begin{array}{c}3\\ 1\end{array}}\right) t(2)+\left( {\begin{array}{c}3\\ 2\end{array}}\right) t(1)+\left( {\begin{array}{c}3\\ 3\end{array}}\right) t(0)\bigg ]\\&\Rightarrow t(4)> 3\times 171+2\bigg [3\times 13+3\times 2+1\times 1\bigg ]\\&\Rightarrow t(4)> 605\\ \end{aligned}$$