A007297 - OEIS

%I M3594 #140 Oct 29 2023 21:51:20

%S 1,1,4,23,156,1162,9192,75819,644908,5616182,49826712,448771622,

%T 4092553752,37714212564,350658882768,3285490743987,30989950019532,

%U 294031964658430,2804331954047160,26870823304476690,258548658860327880

%N Number of connected graphs on n labeled nodes on a circle with straight-line edges that don't cross.

%C Apart from the initial 1, reversion of g.f. for A162395 (squares with signs): see A263843.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H N. J. A. Sloane, <a href="/A007297/b007297.txt">Table of n, a(n) for n = 1..999</a> (first 101 terms from T. D. Noe)

%H M. Aguiar and J.-L. Loday, <a href="http://dx.doi.org/10.1016/j.jpaa.2004.01.002">Quadri-algebras</a>, J. Pure Appl. Algebra, 191 (2004), 205-221.

%H R. Bacher, <a href="http://arxiv.org/abs/math/0409050">On generating series of complementary plane trees</a> arXiv:math/0409050 [math.CO], 2004.

%H P. Barry and A. Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry1/barry202.html">Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays</a>, Journal of Integer Sequences, 2012, article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012

%H F. R. Bernhart & N. J. A. Sloane, <a href="/A006343/a006343.pdf">Emails, April-May 1994</a>

%H F. Cazals, <a href="http://algo.inria.fr/libraries/autocomb/NCC-html/NCC.html">Combinatorics of Non-Crossing Configurations</a>, Studies in Automatic Combinatorics, Volume II (1997).

%H E. Deutsch and B. E. Sagan, <a href="https://arxiv.org/abs/math/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.

%H C. Domb and A. J. Barrett, <a href="http://dx.doi.org/10.1016/0012-365X(74)90081-8">Enumeration of ladder graphs</a>, Discrete Math. 9 (1974), 341-358 (column sums in Table 2).

%H Michael Drmota, Anna de Mier, Marc Noy, <a href="http://www.dmg.tuwien.ac.at/drmota/noncrossingFinal4.pdf">Extremal statistics on non-crossing configurations</a>, Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (3). - N. J. A. Sloane, May 18 2014

%H Guillermo Esteban, Clemens Huemer, Rodrigo I. Silveira, <a href="https://arxiv.org/abs/2003.00524">New production matrices for geometric graphs</a>, arXiv:2003.00524 [math.CO], 2020.

%H Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, <a href="http://dx.doi.org/10.1111/j.1467-9590.2006.00337.x">On the congruences of some combinatorial numbers</a>, Stud. Appl. Math. vol. 116 (2006) pp. 135-144.

%H P. Flajolet and M. Noy, <a href="http://algo.inria.fr/flajolet/Publications">Analytic Combinatorics of Non-crossing Configurations</a>

%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of non-crossing configurations</a>, Discrete Math., 204, 203-229, 1999.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 486.

%H Loïc Foissy, <a href="http://arxiv.org/abs/1504.06056">Free quadri-algebras and dual quadri-algebras</a>, arXiv:1504.06056 [math.CO], 2015.

%H I. M. Gessel, <a href="http://arxiv.org/abs/1403.7656">A short proof of the Deutsch-Sagan congruence for connected non crossing graphs</a>, arXiv preprint arXiv:1403.7656 [math.CO], 2014.

%H Marco Kuhlmann, <a href="http://arxiv.org/abs/1504.04993">Tabulation of Noncrossing Acyclic Digraphs</a>, arXiv:1504.04993 [cs.DS], 2015.

%H M. Kuhlmann, P. Jonsson, <a href="https://doi.org/10.1162/tacl_a_00158">Parsing to Noncrossing Dependency Graphs</a>, Transactions of the Association for Computational Linguistics, vol. 3, pp. 559-570, 2015.

%H Sara Madariaga, <a href="http://arxiv.org/abs/1304.5184">Gröbner-Shirshov bases for the non-symmetric operads of dendriform algebras and quadri-algebras</a>, arXiv:1304.5184 [math.RA], 2013.

%H B. Vallette, <a href="http://arxiv.org/abs/math/0609002">Manin products, Koszul duality, Loday algebras and Deligne conjecture</a>, arXiv:math/0609002 [math.QA], 2006-2007; J. Reine Angew. Math. 620 (2008), 105-164.

%H Gus Wiseman, <a href="/A007297/a007297.png">The a(5) = 156 connected non-crossing graphs</a>.

%H Gus Wiseman, <a href="/A007297/a007297.txt">Constructive Mathematica program for A007297</a>.

%H Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, <a href="https://arxiv.org/abs/1706.03357">Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing</a>, arXiv:1706.03357 [cs.CL], 2017.

%H <a href="/index/Res#revert">Index entries for reversions of series</a>

%F Apart from initial term, g.f. is the series reversion of (x-x^2)/(1+x)^3 (A162395). See A263843. - _Vladimir Kruchinin_, Feb 08 2013

%F G.f.: (g-z)/z, where g=-1/3+(2/3)*sqrt(1+9z)*sin((1/3)*arcsin((2+27z+54z^2)/2/(1+9*z)^(3/2))). - _Emeric Deutsch_, Dec 02 2002

%F a(n) = (1/n)*Sum_{k=0..n} binomial(3n, n-k-1)*binomial(n+k-1, k). - _Paul Barry_, May 11 2005

%F a(n) = 4^(n-1)*(Gamma(3*n/2-1)/Gamma(n/2+1)/Gamma(n) -Gamma((3*n-1)/2)/ Gamma( (n+1)/2)/Gamma(n+1)). - _Mark van Hoeij_, Aug 27 2005, adapted to offset Feb 21 2020 by _R. J. Mathar_

%F a(n) = 4^n * binomial(3*n/2, n/2) / (9*n-6) - 4^(n-1) * binomial(3*(n-1)/2, (n-1)/2 ) / n. - _Mark van Hoeij_, Aug 27 2005, adapted to offset Feb 21 2020 by _R. J. Mathar_

%F D-finite with recurrence: n*(n-1)*(3*n-4)*a(n) +36*(n-1)*a(n-1) -12*(3*n-8)*(3*n-1)*(3*n-7)*a(n-2)=0. - _Mark van Hoeij_, Aug 27 2005, adapted to offset Feb 21 2020 by _R. J. Mathar_

%F a(n) = (1/n)*Sum_{k=0..n} C(3n, k)*C(2n-k-2, n-1). - _Paul Barry_, Sep 27 2005

%F a(n) ~ (2-sqrt(3)) * 6^n * 3^(n/2) / (sqrt(2*Pi) * n^(3/2)). - _Vaclav Kotesovec_, Mar 17 2014

%F a(n) = binomial(3*n,2*n+1)*hypergeom([1-n,n], [2*n+2], -1)/n. - _Vladimir Reshetnikov_, Oct 25 2015

%F a(n) = 2*A078531(n) - A085614(n+1). - _Vladimir Reshetnikov_, Apr 24 2016

%e G.f. = x*(1 + x + 4*x^2 + 23*x^3 + 156*x^4 + 1162*x^5 + 9192*x^6 + 75819*x^7 + ...).

%p A007297:=proc(n) if n = 1 then 1 else add(binomial(3*n - 3, n + j)*binomial(j - 1, j - n + 1), j = n - 1 .. 2*n - 3)/(n - 1); fi; end;

%t CoefficientList[ InverseSeries[ Series[(x-x^2)/(1+x)^3, {x, 0, 20}], x], x] // Rest (* From _Jean-François Alcover_, May 19 2011, after PARI prog. *)

%t Table[Binomial[3n, 2n+1] Hypergeometric2F1[1-n, n, 2n+2, -1]/n, {n, 1, 20}] (* _Vladimir Reshetnikov_, Oct 25 2015 *)

%o (PARI) a(n)=if(n<0,0,polcoeff(serreverse((x-x^2)/(1+x)^3+O(x^(n+2))),n+1)) /* _Ralf Stephan_ */

%Y Cf. A162395, A000290. 4th row of A107111. Row sums of A089434.

%Y See A263843 for a variant.

%Y Cf. A000108 (non-crossing set partitions), A001006, A001187, A054726 (non-crossing graphs), A054921, A099947, A194560, A293510, A323818, A324167, A324169, A324173.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_, _Mira Bernstein_

%E Better description from _Philippe Flajolet_, Apr 20 2000

%E More terms from _James A. Sellers_, Aug 21 2000

%E Definition revised and initial a(1)=1 added by _N. J. A. Sloane_, Nov 05 2015 at the suggestion of _Axel Boldt_. Some of the formulas may now need to be adjusted slightly.