login
The OEIS is supported by the many generous donors 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.
LINKS
P. Flajolet and M. Noy, Analytic Combinatorics of Noncrossing Configurations, Discr. Math. 204 (1999), 203-229.
FORMULA
T(n,k) = 2^(k-1)*(k*L(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_{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).
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
Sequence in context: A010765 A193477 A193726 * A154100 A002880 A225465
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 07:20 EDT 2024. Contains 371235 sequences. (Running on oeis4.)