|
Search: id:A094046
|
|
|
| A094046 |
|
Triangle read by rows: T(n,k) (n>=2; 0<=k<=floor(n/2)-1) is the number of noncrossing connected graphs on n nodes on a circle, having exactly k four-sided faces. |
|
+0
1
|
|
| 1, 4, 22, 1, 141, 15, 988, 171, 3, 7337, 1778, 77, 56749, 17758, 1300, 12, 452332, 173826, 18315, 435, 3689697, 1683055, 233695, 9680, 55, 30652931, 16195344, 2804637, 171226, 2574, 258465558, 155280489, 32306742, 2647580, 70980, 273
(list; graph; listen)
|
|
|
OFFSET
|
2,2
|
|
|
COMMENT
|
T(2n,n-1)=A001764(n-1); T(n,0)=A045744(n)
|
|
REFERENCES
|
P. Flajolet and M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math. 204 (1999), 203-229.
|
|
FORMULA
|
T(n, k)=binomial(n+k-2, k)*sum(binomial(n+k+i-2, i)*binomial(4n-4-k-i, n-2k-2-3i), i=0..floor((n-2k-2)/3))/(n-1). G.f.=G=G(t, z) satisfies G=z(1+G)^5/(1+G-G^3-tG^2).
|
|
EXAMPLE
|
T(5,1)=15 because on the nodes A,B,C,D,E we have three connected noncrossing graphs having BCDE as the unique four-sided face: {AB,BC,CD,DE,EB}, {AE,BC,CD,DE,EB} and {AB,AE,BC,CD,DE,EB}; by circular permutations we obtain 5*3=15.
|
|
MAPLE
|
T:=proc(n, k) if n=1 and k=0 then 1 elif n=1 and k>0 then 0 else binomial(n+k-2, k)*sum(binomial(n+k+i-2, i)*binomial(4*n-4-k-i, n-2*k-2-3*i), i=0..floor((n-2*k-2)/3))/(n-1) fi end: seq(seq(T(n, k), k=0..floor(n/2)-1), n=2..15);
|
|
CROSSREFS
|
Sequence in context: A158947 A000868 A000875 this_sequence A121006 A043061 A009925
Adjacent sequences: A094043 A094044 A094045 this_sequence A094047 A094048 A094049
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), May 31 2004
|
|
|
Search completed in 0.002 seconds
|
