A045743 Number of noncrossing connected graphs on n nodes on a circle having no triangular faces.

1, 3, 13, 66, 367, 2164, 13293, 84157, 545270, 3598244, 24100375, 163416748, 1119592052, 7738412716, 53894849437, 377851866954, 2664570714233, 18887568709788, 134501247038230, 961774761388430, 6903072966224220

Offset

2,2

Links

Andrew Howroyd, Table of n, a(n) for n = 2..200

Formula

a(n) = Sum_{i=0..floor((n-2)/2)} binomial(n-2+i, i)*binomial(3*n-3-i, n-2-2*i)/(n-1).

From Paul D. Hanna, Mar 09 2010: (Start)

G.f. A(x): Let F(x) = 1 + A(x)/x = 1 + x + 3*x^2 + 13*x^3 + 66*x^4 +...

then F(x) satisfies: x*F(x)^4 = (1 - F(x))*(1 - 3*F(x) + F(x)^2). (End)

Conjecture D-finite with recurrence 5*n*(n-1)*(n-2)*(1353818*n-3651663)*a(n) +16*(n-1)*(n-2)*(2236406*n^2-6864025*n+2014500)*a(n-1) -16*(n-2)*(46338048*n^3-326486432*n^2+734160494*n-506411475)*a(n-2) +8*(2*n-7)*(26592864*n^3-436441232*n^2+2071128458*n-3030735075)*a(n-3) +128*(94246*n-334675)*(4*n-19)*(2*n-9)*(4*n-17)*a(n-4)=0. - R. J. Mathar, Jul 26 2022

Prog

(PARI) {a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=1-x*A^4/(1-3*A+A^2)); polcoeff(A, n)} \\ Paul D. Hanna, Mar 09 2010
(PARI) a(n) = if(n>1, sum(i=0, floor(n/2)-1, binomial(n-2+i, i)*binomial(3*n-3-i, n-2-2*i))/(n-1)); \\ Andrew Howroyd, Nov 12 2017

Crossrefs

Column k=0 of A089435.

Cf. A045744.

Sequence in context: A228987 A112807 A219537 * A110530 A142979 A302303

Adjacent sequences: A045740 A045741 A045742 * A045744 A045745 A045746

Keyword

nonn

Author

Emeric Deutsch

Status

approved