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.

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

Offset

2,2

Comments

T(2n,n-1) = A001764(n-1); T(n,0) = A045744(n).

Links

Table of n, a(n) for n=2..37.

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);

Mathematica

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, (n-2k-2)/3}]/(n-1);
Table[T[n, k], {n, 2, 15}, {k, 0, n/2-1}] // Flatten (* Jean-François Alcover, Jul 29 2018 *)

Crossrefs

Sequence in context: A158947 A000868 A000875 * A326603 A335697 A121006

Adjacent sequences: A094043 A094044 A094045 * A094047 A094048 A094049

Keyword

nonn,tabf

Author

Emeric Deutsch, May 31 2004

Status

approved