|
Search: id:A143022
|
|
|
| A143022 |
|
Triangle read by rows: T(n,k) is the number of non-crossing connected graphs on n nodes on a circle in which the root (a distinguished node) has degree k (n>=2, 1<= k<=n-1). |
|
+0
2
|
|
| 1, 2, 2, 9, 10, 4, 54, 62, 32, 8, 374, 436, 248, 88, 16, 2820, 3316, 1984, 816, 224, 32, 22485, 26586, 16404, 7320, 2416, 544, 64, 186494, 221350, 139424, 65512, 24032, 6688, 1280, 128, 1592778, 1895740, 1211848, 590040, 231824, 73088, 17664, 2944
(list; table; graph; listen)
|
|
|
OFFSET
|
2,2
|
|
|
COMMENT
|
Row sums yield A007297.
T(n,1)=A089436(n).
Sum(k*T(n,k),k=1..n-1)=A143023.
|
|
REFERENCES
|
P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203-229.
|
|
FORMULA
|
T(n,k)=2^(k-1)*[kL(n-k-1,3n-k-4,n-2) - L(n-k-2,3n-k-3,n-1)/(n-1) (n>=2, 1<=k<=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. = G(t,z)=g[z-t(g-z)]/[g - 2t(g - z)], where g=g(z), the g.f. for the number of non-crossing connected graphs on n nodes on a circle, satisfies g^3 + g^2 -3zg +2z^2=0 (A007297).
|
|
EXAMPLE
|
T(3,1)=2, T(3,2)=2 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the node A has degrees 2, 2, 1 and 1, respectively.
Triangle starts:
1;
2,2;
9,10,4;
54,62,32,8;
374,436,248,88,16
|
|
MAPLE
|
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: T:=proc(n, k) options operator, arrow: 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) end proc: for n from 2 to 10 do seq(T(n, k), k=1..n-1) end do; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A007297, A089436, A143023.
Sequence in context: A133920 A059199 A010765 this_sequence A154100 A002880 A066324
Adjacent sequences: A143019 A143020 A143021 this_sequence A143023 A143024 A143025
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 30 2008
|
|
|
Search completed in 0.003 seconds
|
