A143023 Sum of the root degrees over all non-crossing connected graphs on n nodes on a circle (by root we mean a distinguished node).
1, 6, 41, 306, 2422, 19980, 169941, 1479786, 13127114, 118217268, 1077955034, 9932655348, 92342765868, 865126386072, 8159523358029, 77411610053658, 738263424935170, 7073522484902820, 68056887469098990, 657269559836605980
Offset: 2
Keywords
Examples
a(3)=6 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the root, say A, has degrees 2, 2, 1 and 1, respectively.
Links
- Andrew Howroyd, Table of n, a(n) for n = 2..200
- P. Flajolet and M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math. 204 (1999), 203-229.
Programs
-
Maple
eq:=G*(1-G)-z*(1+G)^3: G:=RootOf(eq,G): Gser:=series(z*G*(1+G)/(1-G),z=0,25): seq(coeff(Gser,z,n),n=2..21); # end 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: a:=proc(n) options operator, arrow: (L(n-2,3*n-2, n+1)+L(n-3,3*n-3,n))/(n-1) end proc: seq(a(n),n=2..21);
-
Mathematica
L[p_, q_, r_] := Sum[ Binomial[q, i]*Binomial[r + p - 1 - i, r-1], {i, 0, Min[p, q]}]; t[n_, k_] := 2^(k-1)*(k*L[n - k - 1, 3*n - k - 4, n - 2] - L[n - k - 2, 3*n - k - 3, n-1])/(n-1); t[2, 1] = 1; a[n_] := Sum[ k*t[n, k], {k, 1, n-1}]; Table[a[n], {n, 2, 21}] (* Jean-François Alcover, Oct 05 2011, after Maple *) -
PARI
{my(n=25); my(g=serreverse(x*(1-x)/(1+x)^3 + O(x*x^n))); Vec(g*(1+g)/(1-g))} \\ Andrew Howroyd, Dec 22 2017
Formula
a(n) = (L(n-2, 3n-2, n+1) + L(n-3, 3n-3, n))/(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.: zG(1+G)/(1-G) where G=G(z) satisfies G(1-G)=z(1+G)^3.
a(n) = Sum_{k=1..n-1} k*A143022(n,k).
D-finite with recurrence 5*n*(n-1)*a(n) -18*(n-1)*(n-3)*a(n-1) +12*(-45*n^2+180*n-178)*a(n-2) +216*(3*n-10)*(3*n-11)*a(n-3)=0. - R. J. Mathar, Jul 26 2022
Comments