The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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*(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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 11 01:53 EDT 2020. Contains 336418 sequences. (Running on oeis4.)