login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 3
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,2

COMMENTS

Row sums yield A007297.

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

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

REFERENCES

P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203-229.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 2..1276

FORMULA

T(n,k)=2^(k-1)*[kL(n-k-1,3n-k-4,n-2) - L(n-k-2,3n-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[binom(q,i)binom(r+p-1-i,r-1),i=0..min(p,q)].

G.f.: G(t,z)=g[z-t(g-z)]/[g - 2t(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 -3zg +2z^2=0 (A007297).

EXAMPLE

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;

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

PROG

(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

CROSSREFS

Cf. A007297, A089436, A143023.

Sequence in context: A010765 A193477 A193726 * A154100 A002880 A225465

Adjacent sequences:  A143019 A143020 A143021 * A143023 A143024 A143025

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jul 30 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 09:52 EST 2019. Contains 319363 sequences. (Running on oeis4.)