|
%I #35 Apr 11 2020 10:20:12
%S 6,152,940,3600,10570,26096,56952,113280,209550,365640,608036,971152,
%T 1498770,2245600,3278960,4680576,6548502,8999160,12169500,16219280,
%U 21333466,27724752,35636200,45344000,57160350,71436456,88565652,108986640,133186850,161705920
%N Number of consistent sets of 3 irreflexive binary order relationships over n objects.
%C From _Petros Hadjicostas_, Apr 10 2020: (Start)
%C 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.
%C 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.
%C 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.
%C The two groups of excluded 3-sets do not overlap, and the formula has been proved.
%C 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.
%C (End)
%H V. I. Rodionov, <a href="https://doi.org/10.1016/0012-365X(92)90155-9">On the number of labeled acyclic digraphs</a>, Discr. Math. 105 (1-3) (1992), 319-321.
%F 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
%F Conjectures from _Colin Barker_, Apr 11 2020: (Start)
%F G.f.: 2*x^3*(3 + 55*x + x^2 + x^3) / (1 - x)^7.
%F 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.
%F (End)
%e From _Petros Hadjicostas_, Apr 10 2020: (Start)
%e 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)
%p a := n -> (1/6)*n*(n-1)*(n-2)*(n^3-5*n-6):
%p seq(a(n), n=3..32); # _Peter Luschny_, Apr 11 2020
%Y 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).
%Y Column k = 3 of A081064.
%K nonn
%O 3,1
%A _R. H. Hardin_, May 04 2009
%E More terms from _Vaclav Kotesovec_, Apr 11 2020
%E Offset changed to n=3 by _Petros Hadjicostas_, Apr 11 2020
|
