|
| |
|
|
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, 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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 2,2
|
|
|
COMMENTS
| 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 * A121006 A185866 A043061
Adjacent sequences: A094043 A094044 A094045 * A094047 A094048 A094049
|
|
|
KEYWORD
| nonn,tabf
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), May 31 2004
|
| |
|
|
