login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007297 Number of connected graphs on n labeled nodes on a circle with straight-line edges that don't cross.
(Formerly M3594)
28
1, 1, 4, 23, 156, 1162, 9192, 75819, 644908, 5616182, 49826712, 448771622, 4092553752, 37714212564, 350658882768, 3285490743987, 30989950019532, 294031964658430, 2804331954047160, 26870823304476690, 258548658860327880 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

REFERENCES

M Kuhlmann, P Jonsson, Parsing to Noncrossing Dependency Graphs, Transactions of the Association for Computational Linguistics, vol. 3, pp. 559-570, 2015.

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

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 1..999, Nov 05 2015 [First 101 terms from T. D. Noe]

M. Aguiar and J.-L. Loday, Quadri-algebras, J. Pure Appl. Algebra, 191 (2004), 205-221.

R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.

P. Barry and A. Hennessy, Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, 2012, article 12.4.2. - From N. J. A. Sloane, Sep 21 2012

F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994

F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).

C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358 (column sums in Table 2).

E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.

Michael Drmota, Anna de Mier, Marc Noy, Extremal statistics on non-crossing configurations, Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (3). - N. J. A. Sloane, May 18 2014

Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, On the congruences of some combinatorial numbers, Stud. Appl. Math. vol. 116 (2006) pp. 135-144

P. Flajolet and M. Noy, Analytic Combinatorics of Non-crossing Configurations

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486

Loïc Foissy, Free quadri-algebras and dual quadri-algebras, arXiv:1504.06056 [math.CO], 2015.

I. M. Gessel, A short proof of the Deutsch-Sagan congruence for connected non crossing graphs, arXiv preprint arXiv:1403.7656 [math.CO], 2014.

Marco Kuhlmann, Tabulation of Noncrossing Acyclic Digraphs, arXiv:1504.04993 [cs.DS], 2015.

Sara Madariaga, Gröbner-Shirshov bases for the non-symmetric operads of dendriform algebras and quadri-algebras, arXiv:1304.5184 [math.RA], 2013.

B. Vallette, Manin products, Koszul duality, Loday algebras and Deligne conjecture, J. Reine Angew. Math. 620 (2008), 105-164.

Gus Wiseman, The a(5) = 156 connected non-crossing graphs.

Gus Wiseman, Constructive Mathematica program for A007297.

Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing, arXiv:1706.03357 [cs.CL], 2017.

Index entries for reversions of series

FORMULA

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

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

a(n) = (1/n)*Sum_{k=0..n} binomial(3n, n-k-1)*binomial(n+k-1, k). - Paul Barry, May 11 2005

a(n) = 4^n*(Gamma((3*n+1)/2)/Gamma((n+3)/2)/Gamma(n+1) -Gamma(3*n/2+1)/ Gamma( n/2 +1)/Gamma(n+2)). - Mark van Hoeij, Aug 27 2005

C := binomial; a(n) = 4^(n+1) * C(3*(n+1)/2, (n+1)/2) / (9*n+3) - 4^n * C(3*n/2, n/2 ) / (n+1). - Mark van Hoeij, Aug 27 2005

-12*(3*n+2)*(3*n+1)*(3*n+8)*a(n)+(72+36*n)*a(n+1)+(3*n+5)*(n+3)*(n+2)*a(n+2) = 0. - Mark van Hoeij, Aug 27 2005

a(n) = (1/n)*Sum_{k=0..n} C(3n, k)*C(2n-k-2, n-1). - Paul Barry, Sep 27 2005

a(n) ~ (2-sqrt(3)) * 6^n * 3^(n/2) / (sqrt(2*Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 17 2014

a(n) = binomial(3*n,2*n+1)*hypergeom([1-n,n], [2*n+2], -1)/n. - Vladimir Reshetnikov, Oct 25 2015

a(n) = 2*A078531(n) - A085614(n+1). - Vladimir Reshetnikov, Apr 24 2016

EXAMPLE

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

MAPLE

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;

MATHEMATICA

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. *)

Table[Binomial[3n, 2n+1] Hypergeometric2F1[1-n, n, 2n+2, -1]/n, {n, 1, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)

PROG

(PARI) a(n)=if(n<0, 0, polcoeff(serreverse((x-x^2)/(1+x)^3+O(x^(n+2))), n+1)) /* Ralf Stephan */

CROSSREFS

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

See A263843 for a variant.

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

Sequence in context: A246813 A055723 A271469 * A263843 A198916 A182969

Adjacent sequences:  A007294 A007295 A007296 * A007298 A007299 A007300

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane, Mira Bernstein

EXTENSIONS

Better description from Philippe Flajolet, Apr 20 2000

More terms from James A. Sellers, Aug 21 2000

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.

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 08:00 EST 2019. Contains 320420 sequences. (Running on oeis4.)