cp's OEIS Frontend

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.

%I A094046 #9 Jul 29 2018 08:09:21
%S A094046 1,4,22,1,141,15,988,171,3,7337,1778,77,56749,17758,1300,12,452332,
%T A094046 173826,18315,435,3689697,1683055,233695,9680,55,30652931,16195344,
%U A094046 2804637,171226,2574,258465558,155280489,32306742,2647580,70980,273
%N 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.
%C A094046 T(2n,n-1) = A001764(n-1); T(n,0) = A045744(n).
%H A094046 P. Flajolet and M. Noy, <a href="https://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of noncrossing configurations</a>, Discrete Math. 204 (1999), 203-229.
%F A094046 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).
%F A094046 G.f. G=G(t, z) satisfies: G = z(1+G)^5/(1+G-G^3-tG^2).
%e A094046 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.
%p A094046 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);
%t A094046 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);
%t A094046 Table[T[n, k], {n, 2, 15}, {k, 0, n/2-1}] // Flatten (* _Jean-François Alcover_, Jul 29 2018 *)
%K A094046 nonn,tabf
%O A094046 2,2
%A A094046 _Emeric Deutsch_, May 31 2004