A143022 Triangle read by rows: T(n,k) is the number of non-crossing connected graphs on n nodes on a circle in which the root (a distinguished node) has degree k (n >= 2, 1 <= k <= n-1).

1, 2, 2, 9, 10, 4, 54, 62, 32, 8, 374, 436, 248, 88, 16, 2820, 3316, 1984, 816, 224, 32, 22485, 26586, 16404, 7320, 2416, 544, 64, 186494, 221350, 139424, 65512, 24032, 6688, 1280, 128, 1592778, 1895740, 1211848, 590040, 231824, 73088, 17664, 2944

Offset: 2

Author

Emeric Deutsch, Jul 30 2008

Keywords

• nonn
• tabl

Comments

Row sums yield A007297.

T(n,1) = A089436(n).

Sum_{k=1..n-1} k*T(n,k) = A143023.

Examples

			T(3,1)=2, T(3,2)=2 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the node A has degrees 2, 2, 1 and 1, respectively.
Triangle starts:
     1;
     2,    2;
     9,   10,    4;
    54,   62,   32,   8;
   374,  436,  248,  88,  16;
  2820, 3316, 1984, 816, 224, 32;
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 2..1276
• P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203-229.

Crossrefs

Cf. A007297, A089436, A143023.

Programs

Maple

L:=proc(p,q,r) options operator, arrow: sum(binomial(q, i)*binomial(r+p-1-i, r-1), i=0..min(p, q)) end proc: T:=proc(n,k) options operator, arrow: 2^(k-1)*(k*L(n-k-1,3*n-k-4,n-2)-L(n-k-2,3*n-k-3,n-1))/(n-1) end proc: for n from 2 to 10 do seq(T(n,k),k=1..n-1) end do; # yields sequence in triangular form

Mathematica

L[p_, q_, r_] := Sum[Binomial[q, i]*Binomial[r + p - 1 - i, r-1], {i, 0, Min[p, q]}]; t[n_, k_] := 2^(k-1)*(k*L[n - k - 1, 3*n - k - 4, n - 2] - L[n - k - 2, 3*n - k - 3, n-1])/(n-1); t[2, 1] = 1; Flatten[ Table[t[n, k], {n, 2, 10}, {k, 1, n-1}]] (* Jean-François Alcover, Oct 05 2011, after Maple *)

PARI

L(p,q,r)={sum(i=0, min(p,q), binomial(q,i)*binomial(r+p-1-i,r-1))}
T(n,k)={if(n<3, n==2&&k==1, 2^(k-1)*(k*L(n-k-1, 3*n-k-4, n-2) - L(n-k-2, 3*n-k-3, n-1))/(n-1))}
for(n=2, 10, for(k=1, n-1, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017

PARI

S(n)={my(g=x+x*serreverse((x-x^2)/(1+x)^3 + O(x^n))); Vec(g*(x - y*(g-x))/(g - 2*y*(g - x)))}
my(v=S(10)); for(n=2, #v, my(p=v[n]); for(k=1, n-1, print1(polcoeff(p,k), ", ")); print) \\ Andrew Howroyd, Nov 17 2017

Formula

T(n,k) = 2^(k-1)*(k*L(n-k-1, 3*n-k-4, n-2) - L(n-k-2, 3*n-k-3, n-1))/(n-1) (n >= 2, 1 <= k <= n-1), where L(p,q,r) = [u^p](1+u)^q/(1-u)^r = Sum_{i=0..min(p,q)} binomial(q,i)*binomial(r+p-1-i, r-1).

G.f.: G(t,z) = g*(z - t*(g-z))/(g - 2*t*(g-z)), where g=g(z), the g.f. for the number of non-crossing connected graphs on n nodes on a circle, satisfies g^3 + g^2 - 3*z*g + 2*z^2 = 0 (A007297).