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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A143018 Triangle read by rows: T(n,k) (n >=2, k >=1) is the number of non-crossing connected graphs on n nodes on a circle such that the distance from a fixed node (root) to the next node is k. Rows are indexed 2,3,4,...; columns are indexed 1,2,3, ... . 3

%I

%S 1,3,1,16,6,1,105,41,9,1,768,306,75,12,1,6006,2422,630,118,15,1,49152,

%T 19980,5394,1104,170,18,1,415701,169941,47061,10197,1755,231,21,1,

%U 3604480,1479786,417439,94116,17425,2610,301,24,1

%N Triangle read by rows: T(n,k) (n >=2, k >=1) is the number of non-crossing connected graphs on n nodes on a circle such that the distance from a fixed node (root) to the next node is k. Rows are indexed 2,3,4,...; columns are indexed 1,2,3, ... .

%C Row sums yield A007297.

%C T(n,1) = A085614(n-1).

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

%H Andrew Howroyd, <a href="/A143018/b143018.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>, Discrete Math. 204 (1999), 203-229.

%F T(n,k) = k*L(n-k-1,3n-k-4,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)].

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

%F T(n,k) = k*Sum_{i=0..min(n-k-1, 3*n-k-4)} binomial(3*n-k-4, i)*binomial(2*n-k-i-3, n-2)/(n-1). - _Andrew Howroyd_, Nov 17 2017

%e T(3,1)=3 and T(3,2)=1 because in the graphs (AB,BC,CA), (AB,AC), (AB,BC) and (AC,BC) the distances from A to B are 1, 1, 1 and 2, respectively.

%e Triangle starts:

%e 1;

%e 3, 1;

%e 16, 6, 1;

%e 105, 41, 9, 1;

%e 768, 306, 75, 12, 1;

%e ...

%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: k*L(n-k-1, 3*n-k-4, 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 t[n_, k_] := k*L[n - k - 1, 3*n - k - 4, n-1]/(n-1); L[p_, q_, r_] := Sum[ Binomial[q, i]*Binomial[r + p - 1 - i, r-1], {i, 0, Min[p, q]}]; Flatten[ Table[ t[n, k], {n, 2, 10}, {k, 1, n-1}]] (* _Jean-Fran├žois Alcover_, Oct 05 2011, Oct 05 2011, after Maple *)

%o (PARI)

%o T(n,k)=k*sum(i=0, min(n-k-1, 3*n-k-4), binomial(3*n-k-4, i)*binomial(2*n-k-i-3, n-2))/(n-1);

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

%Y Cf. A085614, A143020, A007297.

%K nonn,tabl

%O 2,2

%A _Emeric Deutsch_, Jul 30 2008

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 February 16 18:53 EST 2019. Contains 320165 sequences. (Running on oeis4.)