A085614 -id:A085614 - cp's OEIS frontend

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

1, 1, 4, 23, 156, 1162, 9192, 75819, 644908, 5616182, 49826712, 448771622, 4092553752, 37714212564, 350658882768, 3285490743987, 30989950019532, 294031964658430, 2804331954047160, 26870823304476690, 258548658860327880

Offset: 1

N. J. A. Sloane, Mira Bernstein

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

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

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

N. J. A. Sloane, Table of n, a(n) for n = 1..999 (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).
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.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358 (column sums in Table 2).
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
Guillermo Esteban, Clemens Huemer, Rodrigo I. Silveira, New production matrices for geometric graphs, arXiv:2003.00524 [math.CO], 2020.
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.
M. Kuhlmann, P. Jonsson, Parsing to Noncrossing Dependency Graphs, Transactions of the Association for Computational Linguistics, vol. 3, pp. 559-570, 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, arXiv:math/0609002 [math.QA], 2006-2007; 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

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.

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;

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

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

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

Better description from Philippe Flajolet, Apr 20 2000
More terms from James 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.

A143018 Triangle read by rows: T(n,k) (n >= 2, k >= 1) is the number of non-crossing connected graphs on n nodes on a circle such that the distance from a fixed node (root) to the next node is k. Rows are indexed 2,3,4,...; columns are indexed 1,2,3, ... .

Original entry on oeis.org

1, 3, 1, 16, 6, 1, 105, 41, 9, 1, 768, 306, 75, 12, 1, 6006, 2422, 630, 118, 15, 1, 49152, 19980, 5394, 1104, 170, 18, 1, 415701, 169941, 47061, 10197, 1755, 231, 21, 1, 3604480, 1479786, 417439, 94116, 17425, 2610, 301, 24, 1

Offset: 2

Emeric Deutsch, Jul 30 2008

Row sums yield A007297.
T(n,1) = A085614(n-1).
Sum_{k=1..n-1} k*T(n,k) = A143020(n).

			T(3,1)=3 and T(3,2)=1 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the distances from A to B are 1, 1, 1 and 2, respectively.
Triangle starts:
    1;
    3,   1;
   16,   6,  1;
  105,  41,  9,  1;
  768, 306, 75, 12, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 2..1276
P. Flajolet and M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math. 204 (1999), 203-229.

Cf. A085614, A143020, A007297.

L:=proc(p,q,r) options operator, arrow: sum(binomial(q, i)*binomial(r+p-1-i, r-1), i=0..min(p,q)) end proc: T:=proc(n,k) options operator, arrow: k*L(n-k-1, 3*n-k-4, n-1)/(n-1) end proc: for n from 2 to 10 do seq(T(n,k),k=1..n-1) end do; # yields sequence in triangular form

t[n_, k_] := k*L[n - k - 1, 3*n - k - 4, n-1]/(n-1); L[p_, q_, r_] := Sum[ Binomial[q, i]*Binomial[r + p - 1 - i, r-1], {i, 0, Min[p, q]}]; Flatten[ Table[ t[n, k], {n, 2, 10}, {k, 1, n-1}]] (* Jean-François Alcover, Oct 05 2011, Oct 05 2011, after Maple *)

T(n,k)=k*sum(i=0, min(n-k-1, 3*n-k-4), binomial(3*n-k-4, i)*binomial(2*n-k-i-3, n-2))/(n-1);
for(n=2, 10, for(k=1, n-1, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017

T(n,k) = k*L(n-k-1, 3n-k-4, n-1)/(n-1) (n >= 2, 1 <= k <= n-1), where L(p,q,r) = [u^p](1+u)^q/(1-u)^r = Sum_{i=0..min(p,q)} binomial(q,i)*binomial(r+p-1-i, r-1).
G.f.: G(t,z) = zg/[g - t*(g - z)], where g=g(z), the g.f. for the number of non-crossing connected graphs on n nodes on a circle, satisfies g^3 + g^2 - 3z*g + 2*z^2 = 0 (A007297).
T(n,k) = k*Sum_{i=0..min(n-k-1, 3*n-k-4)} binomial(3*n-k-4, i)*binomial(2*n-k-i-3, n-2)/(n-1). - Andrew Howroyd, Nov 17 2017

A206300 Expand the real root of y^3 - y + x in powers of x, then multiply coefficient of x^n by -4^n to get integers.

Original entry on oeis.org

-1, 2, 6, 32, 210, 1536, 12012, 98304, 831402, 7208960, 63740820, 572522496, 5209363380, 47915728896, 444799488600, 4161823309824, 39209074920090, 371626340253696, 3541117629057540

Offset: 0

Roger L. Bagula, Feb 05 2012

Also coefficients of the series S(u) for which (-sqrt(3u))*S converges to the larger of the two real roots of x^3 - 3ux + 4u for u >= 4. Specifically, S(u)=Sum_{n>=0} a(n)/(27*u)^(n/2). - Dixon J. Jones, Jun 24 2021

George E. Andrews, Number Theory, 1971, Dover Publications, New York, pp. 41-43.

Cf. A000108, A048990, A224884 (signed version).

Cf. A085614.

p[x_] = y /. Solve[y^3 - y + x == 0, y][[1]]
b = Table[-4^n*FullSimplify[ExpandAll[SeriesCoefficient[ Series[p[x], {x, 0, 30}], n]]], {n, 0, 30}]
Table[2^(2n - 1) Gamma[(3n - 1)/2]/(Gamma[(n + 1)/2]n!), {n, 0, 20}] (* Dixon J. Jones, Jun 24 2021 *)
Table[2^(2n - 1) Pochhammer[(n + 1)/2, (n-1)]/n!, {n, 0, 20}] (* Dixon J. Jones, Jun 24 2021 *)

-x/serreverse((x*sqrt(1-4*x))) \\ Thomas Baruchel, Jul 02 2018

G.f.: -(12*x)/(2*sin(arcsin(216*x^2-1)/3)+1). - Vladimir Kruchinin, Oct 30 2014
G.f.: -x/Revert((x*sqrt(1-4*x))). - Thomas Baruchel, Jul 02 2018
G.f.: - (1/x) * Revert( x*sqrt(c(4*x)) ), where c(x) =  (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108 and sqrt(c(4*x)) is the g.f. of A048990. - Peter Bala, Mar 05 2020
From Dixon J. Jones, Jun 24 2021: (Start)
a(n) = 2*A085614(n) for n>=1.
a(n) = 2^(2*n - 1) Gamma((3*n - 1)/2)/(Gamma((n + 1)/2)*n!).
a(n) = (2^(2*n - 1)*((n + 1)/2)_(n-1))/n!, where (x)_k is the Pochhammer symbol. (End)
a(n) ~ 2^(n-1/2) * 3^(3*n/2-1) / (sqrt(Pi) * n^(3/2)). - Amiram Eldar, Sep 01 2025

Edited by N. J. A. Sloane, Feb 09 2012

A371395 Triangle read by rows: T(n, k) = binomial(n + k, k) * binomial(2*n - k, n - k) / (n + 1).

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 5, 10, 10, 5, 14, 35, 45, 35, 14, 42, 126, 196, 196, 126, 42, 132, 462, 840, 1008, 840, 462, 132, 429, 1716, 3564, 4950, 4950, 3564, 1716, 429, 1430, 6435, 15015, 23595, 27225, 23595, 15015, 6435, 1430

Offset: 0

F. Chapoton, Mar 21 2024

The terms can be seen as graded dimensions of a non-symmetric operad. The Koszul dual operad has Hilbert series x*(1 + x)*(1 + tx). So the current table has as Hilbert series the reverse of x*(1-x)*(1-t*x) w.r.t to x (see Sage below).

The triangle is symmetric under the exchange of k with n - k.

			Triangle begins:
  [0] [ 1],
  [1] [ 1,   1],
  [2] [ 2,   3,   2],
  [3] [ 5,  10,  10,   5],
  [4] [14,  35,  45,  35,  14],
  [5] [42, 126, 196, 196, 126, 42].

Column 0 and main diagonal are A000108.
Column 1 and subdiagonal are A001700.
Row sums are A006013.
The even bisection of the alternating row sums is A001764.
The central terms are A188681.
Cf. A085614, A250886, A371400.

T := (n, k) -> binomial(n + k, k)*binomial(2*n - k, n)/(n + 1):
seq(print(seq(T(n, k), k = 0..n)), n = 0..7);  # Peter Luschny, Mar 21 2024

T[n_, k_] := (Hypergeometric2F1[-n, -k, 1, 1] Hypergeometric2F1[-n, k - n, 1, 1]) /(n + 1); Table[T[n, k], {n, 0, 7}, {k, 0, n}] // Flatten
(* Peter Luschny, Mar 21 2024 *)

def Trow(n):
    return [binomial(n+k, k) * binomial(2*n-k, n-k) / (n+1) for k in range(n+1)]

# As the reverse of x*(1-x)*(1-t*x) w.r.t variable x.
t = polygen(QQ, 't')
x = LazyPowerSeriesRing(t.parent(), 'x').0
gf = x*(1-x)*(1-t*x)
coeffs = gf.revert() / x
for n in range(6):
    print(coeffs[n].list())

From Peter Luschny, Mar 21 2024: (Start)
T(n, k) = hypergeom([-n, -k], [1], 1)*hypergeom([-n, k - n], [1], 1)/(n + 1).
2^n*Sum_{k=0..n} T(n, k)*(1/2)^k = A085614(n + 1).
2^n*Sum_{k=0..n} T(n, k)*(-1/2)^k = A250886(n + 1). (End)

A372506 Coefficient of x^n in the expansion of 1 / ( (1-x) * (1-2*x) )^n.

Original entry on oeis.org

1, 3, 23, 198, 1795, 16758, 159446, 1537308, 14967843, 146833830, 1449054178, 14369723316, 143072565454, 1429331585724, 14320668653580, 143838879376248, 1447883909314851, 14602334949928710, 147518977428892010, 1492559101878005700, 15121898521185194970

Offset: 0

Seiichi Manyama, May 04 2024

nonn

Cf. A001700, A069723, A085614, A255688, A372233.

A372506 := proc(n)
    add(binomial(n+k-1,k)*binomial(3*n-1,n-k),k=0..n) ;
end proc:
seq(A372506(n),n=0..80) ; # R. J. Mathar, Oct 24 2024

Table[SeriesCoefficient[1/((1 - x)*(1 - 2*x))^n, {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, May 04 2024 *)
Table[Binomial[3*n - 1, n] * Hypergeometric2F1[-n, n, 2*n, -1], {n, 0, 20}] (* Vaclav Kotesovec, May 04 2024 *)

a(n, s=1, t=1, u=1) = sum(k=0, n\s, binomial(t*n+k-1, k)*binomial((t+u+1)*n-(s-1)*k-1, n-s*k));

a(n) = Sum_{k=0..n} binomial(n+k-1,k) * binomial(3*n-1,n-k).
The g.f. exp( Sum_{k>=1} a(k) * x^k/k ) has integer coefficients and equals (1/x) * Series_Reversion( x * (1-x) * (1-2*x) ).
a(n) ~ (1 + sqrt(3)) * 2^(n - 3/2) * 3^((3*n-1)/2) / sqrt(Pi*n). - Vaclav Kotesovec, May 04 2024
D-finite with recurrence 5*n*(n-1)*a(n) +18*(n-1)*(n-3)*a(n-1) +12*(-45*n^2+90*n-22)*a(n-2) -216*(3*n-7)*(3*n-8)*a(n-3)=0. - R. J. Mathar, Oct 24 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A143018 Triangle read by rows: T(n,k) (n >= 2, k >= 1) is the number of non-crossing connected graphs on n nodes on a circle such that the distance from a fixed node (root) to the next node is k. Rows are indexed 2,3,4,...; columns are indexed 1,2,3, ... .

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A206300 Expand the real root of y^3 - y + x in powers of x, then multiply coefficient of x^n by -4^n to get integers.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A371395 Triangle read by rows: T(n, k) = binomial(n + k, k) * binomial(2*n - k, n - k) / (n + 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

SageMath

SageMath

Formula

A372506 Coefficient of x^n in the expansion of 1 / ( (1-x) * (1-2*x) )^n.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Formula