|
Search: id:A143023
|
|
|
| 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). |
|
+0
2
|
|
| 1, 6, 41, 306, 2422, 19980, 169941, 1479786, 13127114, 118217268, 1077955034, 9932655348, 92342765868, 865126386072, 8159523358029, 77411610053658, 738263424935170, 7073522484902820, 68056887469098990, 657269559836605980
(list; graph; listen)
|
|
|
OFFSET
|
2,2
|
|
|
COMMENT
|
a(n)=Sum(k*A143022(n,k),k=1..n-1).
The number of non-crossing connected graphs on n nodes on a circle is given in A007297.
|
|
REFERENCES
|
P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203-229.
|
|
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[binom(q,i)binom(r+p-1-i, r-1), i=0..min(p,q)]. G.f. = zG(1+G)/(1-G), where G=G(z) satisfies G(1-G)=z(1+G)^3.
|
|
EXAMPLE
|
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.
|
|
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);
|
|
CROSSREFS
|
Cf. A143022, A007297.
Sequence in context: A083067 A000402 A152107 this_sequence A078009 A127848 A083161
Adjacent sequences: A143020 A143021 A143022 this_sequence A143024 A143025 A143026
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 30 2008
|
|
|
Search completed in 0.002 seconds
|
