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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A143020 Sum of the distances from a fixed node (root) to the next node in all non-crossing graphs on n nodes on a circle. 2
1, 5, 31, 218, 1658, 13293, 110675, 947870, 8297926, 73924162, 668038006, 6108962580, 56426393268, 525673683069, 4933634156571, 46604425575734, 442753710351950, 4227598589181750, 40549714320544770, 390522305786747820 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,2

LINKS

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

P. Flajolet and M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math. 204 (1999), 203-229.

FORMULA

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

G.f.: g(g-z)/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).

a(n) = Sum_{k=1..n-1} k*A143018(n, k).

Conjecture: -(n-1) *(n+1) *(39*n^2-136*n+60) *a(n) +60 *(-18*n^2+57*n-7) *a(n-1) +12 *(3*n-7) *(3*n-8) *(39*n^2-58*n-37) *a(n-2)=0. - R. J. Mathar, May 10 2018

EXAMPLE

a(3)=5 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.

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: k*L(n-k-1, 3*n-k-4, n-1)/(n-1) end proc: seq(add(k*T(n, k), k=1..n-1), n=2..22);

MATHEMATICA

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]}]; a[n_] := Sum[k*t[n, k], {k, 1, n-1}] ; Table[a[n], {n, 2, 21}] (* Jean-Fran├žois Alcover, Oct 05 2011, after Maple *)

PROG

(PARI) Vec((g->g*(g-x)/x)(x + x*serreverse((x-x^2)/(1+x)^3 + O(x^20)))) \\ Andrew Howroyd, Nov 17 2017

(PARI)

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

a(n)=sum(k=1, n-1, k^2*L(n-k-1, 3*n-k-4, n-1)/(n-1)); \\ Andrew Howroyd, Nov 17 2017

CROSSREFS

Cf. A007297, A143018.

Sequence in context: A287899 A110379 A097146 * A059035 A199877 A058309

Adjacent sequences:  A143017 A143018 A143019 * A143021 A143022 A143023

KEYWORD

nonn

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 21 19:51 EST 2019. Contains 319350 sequences. (Running on oeis4.)