A147796 Number of consistent sets of 3 irreflexive binary order relationships over n objects.

6, 152, 940, 3600, 10570, 26096, 56952, 113280, 209550, 365640, 608036, 971152, 1498770, 2245600, 3278960, 4680576, 6548502, 8999160, 12169500, 16219280, 21333466, 27724752, 35636200, 45344000, 57160350, 71436456, 88565652, 108986640, 133186850, 161705920

Offset

3,1

Comments

From Petros Hadjicostas, Apr 10 2020: (Start)

Here is a proof of the formula for a(n). There are n*(n-1) irreflexive binary order relationships among n distinct objects and binomial(n*(n-1), 3) 3-sets of such relationships.

We first exclude the 3-sets that contain both relationships of the form x < y and y < x (with x <> y), and there are (n*(n-1)/2) *(n*(n-1) - 2) such 3-sets.

Next we exclude the 3-sets that contain all the relationships of the form x < y, y < z, and z < x (with x, y, z distinct), and there are 2*binomial(n,3) of these.

The two groups of excluded 3-sets do not overlap, and the formula has been proved.

It seems that a(n) = A081064(n,3) = number of labeled acyclic directed graphs with n nodes and k = 3 arcs (see Rodionov (1992)). The reason is that we may label the graphs with the n objects and draw an arc from X towards Y if and only if X < Y. The 3 arcs of the directed graph correspond to the 3-set of binary order relationships and they are consistent because the directed graph is acyclic.

(End)

Links

Table of n, a(n) for n=3..32.

V. I. Rodionov, On the number of labeled acyclic digraphs, Discr. Math. 105 (1-3) (1992), 319-321.

Formula

a(n) = binomial(n*(n-1), 3) - n*(n-1)*(n*(n-1) - 2)/2 - 2*binomial(n,3) = binomial(n,3) * (n^3 - 5*n - 6). - Petros Hadjicostas, Apr 10 2020

Conjectures from Colin Barker, Apr 11 2020: (Start)

G.f.: 2*x^3*(3 + 55*x + x^2 + x^3) / (1 - x)^7.

a(n) = 7*a(n-1) - 21*a(n-2) + 35*a(n-3) - 35*a(n-4) + 21*a(n-5) - 7*a(n-6) + a(n-7) for n>8.

(End)

Example

From Petros Hadjicostas, Apr 10 2020: (Start)
For n = 3, consider objects a, b, c. There are 3*2 = 6 irreflexive binary order relationships among these objects (a < b, b < a, a < c, c < a, b < c, c < b). For a set of 3 such sets of binary relationships to be consistent, x < y and y < x should not appear together, and x < y, y < z, and z < x should not be together. We have the following sets of 3 such relationships that are consistent: {x < y, y < z, x < z}, where (x,y,z) is in S_3. Thus, a(3) = |S_3| = 3! = 6. (End)

Maple

a := n -> (1/6)*n*(n-1)*(n-2)*(n^3-5*n-6):
seq(a(n), n=3..32); # Peter Luschny, Apr 11 2020

Crossrefs

Related sequences for the number of consistent sets of k irreflexive binary order relationships over n objects: A147817 (k = 4), A147821 (k = 5), A147860 (k = 6), A147872 (k = 7), A147881 (k = 8), A147883 (k = 9), A147964 (k = 10).

Column k = 3 of A081064.

Sequence in context: A297737 A352757 A168654 * A003766 A278728 A221689

Adjacent sequences: A147793 A147794 A147795 * A147797 A147798 A147799

Keyword

nonn

Author

R. H. Hardin, May 04 2009

Extensions

More terms from Vaclav Kotesovec, Apr 11 2020

Offset changed to n=3 by Petros Hadjicostas, Apr 11 2020

Status

approved