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
Keywords
Links
- Andrew Howroyd, Table of n, a(n) for n = 2..200
Programs
-
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
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