

A147796


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


8



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

3,1


COMMENTS

From Petros Hadjicostas, Apr 10 2020: (Start)
Here is a proof of the formula for a(n). There are n*(n1) irreflexive binary order relationships among n distinct objects and binomial(n*(n1), 3) 3sets of such relationships.
We first exclude the 3sets that contain both relationships of the form x < y and y < x (with x <> y), and there are (n*(n1)/2) *(n*(n1)  2) such 3sets.
Next we exclude the 3sets 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 3sets 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 3set 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 (13) (1992), 319321.


FORMULA

a(n) = binomial(n*(n1), 3)  n*(n1)*(n*(n1)  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(n1)  21*a(n2) + 35*a(n3)  35*a(n4) + 21*a(n5)  7*a(n6) + a(n7) 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*(n1)*(n2)*(n^35*n6):
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: A261066 A297737 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



