|
Search: id:A143018
|
|
|
| A143018 |
|
Triangle read by rows: T(n,k) (n >=2, k >=1) is the number of non-crossing connected graphs on n nodes on a circle such that the distance from a fixed node (root) to the next node is k. Rows are indexed 2,3,4,...; columns are indexed 1,2,3, ... . |
|
+0
2
|
|
| 1, 3, 1, 16, 6, 1, 105, 41, 9, 1, 768, 306, 75, 12, 1, 6006, 2422, 630, 118, 15, 1, 49152, 19980, 5394, 1104, 170, 18, 1, 415701, 169941, 47061, 10197, 1755, 231, 21, 1, 3604480, 1479786, 417439, 94116, 17425, 2610, 301, 24, 1
(list; table; graph; listen)
|
|
|
OFFSET
|
2,2
|
|
|
COMMENT
|
Row sums yield A007297.
T(n,1)=A085614(n-1).
Sum(k*T(n,k), k=1..n-1) = A143020(n).
|
|
REFERENCES
|
P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203-229.
|
|
FORMULA
|
T(n,k)=k*L(n-k-1,3n-k-4,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)=zg/[g - t(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)=3 and T(3,2)=1 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the distances from A to B are 1, 1, 1 and 2, respectively.
Triangle starts
1;
3,1;
16,6,1;
105,41,9,1;
768,306,75,12,1
|
|
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: k*L(n-k-1, 3*n-k-4, 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. A085614, A143020, A007297.
Sequence in context: A087071 A053485 A143565 this_sequence A102012 A128249 A071211
Adjacent sequences: A143015 A143016 A143017 this_sequence A143019 A143020 A143021
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 30 2008
|
|
|
Search completed in 0.002 seconds
|
