Why the number of transitive relations is not an integer polynomial

Introduction

Counting is fascinating, but at the same time, challenging. The study of counting, a subject called enumerative combinatorics, is rich in its history and has seen marvels as well as stagnations. This beautiful and breathtaking subject of study pervades with a number of unsolved problems. One among them is the problem of counting transitive relations on n nodes.

A relation R defined on a set X is set to be transitive if ∀x,y,z ∈ X,(x,y) ∈ R,(y,z) ∈ R⇒(x,z) ∈ R. For example, R = {(1,2),(3,6)} is a transitive relation, but R₁ = {(1,2),(2,3)} is not.

Counting all transitive relations on a finite set may seem a straightforward task for sets of small sizes, but for sets with a large number of elements, it is a daunting task. As a matter of fact, given all the work carried out in this direction till date, no formula has been arrived at for counting such relations on a set.

The Online Encyclopedia of Integer Sequences (OEIS) is an online repository of more than 3,50,000 integer sequences. One of these sequences corresponds to the count of these relations on a finite set. Till date, only nineteen entries have been made to the integer sequence corresponding to the count of transitive relations. In addition to the work of others in this direction (1–5), the author of this article has been publishing results in this direction (6–11). The sequence corresponding to the count of transitive relations is available in the online encyclopedia of integer sequences (OEIS), aka Sloane. It’s A-number is A006905.

Main discussion

In what follows, we revisit the proof of the fact that there is no polynomial with integer coefficient that gives the required count of transitive relations t(n) for each n.

Theorem 2.1

Proof: Let $\text{p}(\text{n})={\sum }_{\text{r}=0}^{\text{m}}{\text{a}}_{\text{r}}{\text{n}}^{\text{r}}$ be a polynomial in n.

If possible, let p(n) = t(n), ∀ n ∈ N.

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

The proof follows from equation (2). Since integers cannot add to a fraction, we conclude that not all a_i, 0 ≤ i ≤ m are integers.

That is the required proof.

Al alternative approach

Now, despite the fact that the above proof is concise and simple in its own right, I present a simpler and independent proof of the same fact.

Proof: Note that if a sequence of integers has a polynomial formula, say b₀ + b₁n + b₂n² + ⋯ + b_mn^m, then for any integer k, k must divide a_s−a_s+k, ∀ s ∈ Z.

Now, if there existed a polynomial formula for t(n), then k would divide t(n) − t(n + k), ∀n ∈ N.

However, that is surely not the case as t(3) − t(1) = 171 − 2 = 169 is not even, that is divisible by 2. This completes the proof.

Conflict of interest

The author makes a declaration that this research took place in absence of economic relationships and that there is no conflict of interest to disclose.

Author contributions

This paper is the sole contribution of the author FM.

References