login
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
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
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
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