login
Number of non-crossing connected graphs on n nodes on a circle in which a fixed (distinguished) node has degree one.
4

%I #24 Jul 24 2022 10:15:17

%S 1,2,9,54,374,2820,22485,186494,1592778,13914108,123750874,1116809628,

%T 10201516332,94140605832,876332565837,8219124900558,77594375595266,

%U 736785675010380,7031930543228910,67420537625021460,649070964647075700

%N Number of non-crossing connected graphs on n nodes on a circle in which a fixed (distinguished) node has degree one.

%C Convolution of (1, A007297) with itself.

%H Andrew Howroyd, <a href="/A089436/b089436.txt">Table of n, a(n) for n = 2..200</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.

%F a(n) = Sum_{k=2..2*n-4} 2*binomial(k-2, n-3)*binomial(3*n-5, 2*n-k-4)/(n-2) for n > 2. - _Andrew Howroyd_, Nov 12 2017

%F G.f.: g^2, where g satisfies g^3+g^2-3zg+2z^2=0, g(0)=0, or, in Maple notation, g := -1/3+(2/3)*sqrt(1+9*z)*sin((1/3)*arcsin((2+27*z+54*z^2)/2/(1+9*z)^(3/2))).

%F G.f.: (x+x*g)^2 where g satisfies g - g^2 = x*(1 + g)^3. - _Andrew Howroyd_, Nov 13 2017

%F a(n) ~ 2^(n-1) * 3^(3*n/2-9/4) / (sqrt(Pi)*n^(3/2)*sqrt(45+26*sqrt(3))). - _Vaclav Kotesovec_, Mar 17 2014

%F D-finite with recurrence n*(2*n-3)*(n-2)*a(n) +6*(9*n-10)*a(n-1) -12*(3*n-10)*(3*n-8)*(2*n-1)*a(n-2)=0. - _R. J. Mathar_, May 10 2018

%e a(3)=2 because among the four non-crossing graphs on the points A,B,C, the distinguished node A has degree equal to 1 only in the graphs {AB,BC} and {AC,BC}; in the other two graphs ({AB,AC} and {AB,BC,AC}) the node A has degree 2.

%t terms = 21;

%t g[x_] = 0;

%t Do[g[x_] = g[x]^2 + x (1 + g[x])^3 + O[x]^(terms+2), {terms+2}];

%t Drop[CoefficientList[(x + x g[x])^2 + O[x]^(terms+2), x], 2] (* _Jean-François Alcover_, Oct 05 2011, updated Jul 29 2018 after _Andrew Howroyd_ *)

%o (PARI) a(n)=if(n<3, n==2, sum(k=2, 2*n-4, 2*binomial(k-2, n-3)*binomial(3*n-5, 2*n-k-4))/(n-2)); \\ _Andrew Howroyd_, Nov 12 2017

%o (PARI) Vec((x+x*serreverse((x-x^2)/(1+x)^3 + O(x^25)))^2) \\ _Andrew Howroyd_, Nov 13 2017

%Y Column k=1 of A143022.

%Y Cf. A007297.

%K nonn

%O 2,2

%A _Emeric Deutsch_, Dec 28 2003