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

Author

Emeric Deutsch, May 31 2004

Keywords

• nonn
• tabf

Comments

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

Examples

			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.
		

Links

• P. Flajolet and M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math. 204 (1999), 203-229.

Programs

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

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