A143022 - OEIS

%I #26 Jan 31 2025 23:44:27

%S 1,2,2,9,10,4,54,62,32,8,374,436,248,88,16,2820,3316,1984,816,224,32,

%T 22485,26586,16404,7320,2416,544,64,186494,221350,139424,65512,24032,

%U 6688,1280,128,1592778,1895740,1211848,590040,231824,73088,17664,2944

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

%C Row sums yield A007297.

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

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

%H Andrew Howroyd, <a href="/A143022/b143022.txt">Table of n, a(n) for n = 2..1276</a>

%H P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic Combinatorics of Noncrossing Configurations</a>, Discr. Math. 204 (1999), 203-229.

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

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

%e 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.

%e Triangle starts:

%e      1;

%e      2,    2;

%e      9,   10,    4;

%e     54,   62,   32,   8;

%e    374,  436,  248,  88,  16;

%e   2820, 3316, 1984, 816, 224, 32;

%p 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

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

%o (PARI)

%o L(p,q,r)={sum(i=0, min(p,q), binomial(q,i)*binomial(r+p-1-i,r-1))}

%o 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))}

%o for(n=2, 10, for(k=1, n-1, print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Nov 17 2017

%o (PARI)

%o 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)))}

%o 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

%Y Cf. A007297, A089436, A143023.

%K nonn,tabl,changed

%O 2,2

%A _Emeric Deutsch_, Jul 30 2008