|
%I #20 May 10 2018 09:16:08
%S 1,5,31,218,1658,13293,110675,947870,8297926,73924162,668038006,
%T 6108962580,56426393268,525673683069,4933634156571,46604425575734,
%U 442753710351950,4227598589181750,40549714320544770,390522305786747820
%N Sum of the distances from a fixed node (root) to the next node in all non-crossing graphs on n nodes on a circle.
%H Andrew Howroyd, <a href="/A143020/b143020.txt">Table of n, a(n) for n = 2..200</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 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).
%F 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).
%F a(n) = Sum_{k=1..n-1} k*A143018(n, k).
%F 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
%e 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.
%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: seq(add(k*T(n,k),k=1..n-1),n=2..22);
%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]}]; 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 *)
%o (PARI) Vec((g->g*(g-x)/x)(x + x*serreverse((x-x^2)/(1+x)^3 + O(x^20)))) \\ _Andrew Howroyd_, Nov 17 2017
%o (PARI)
%o L(p,q,r)={sum(i=0, min(p,q), binomial(q,i)*binomial(r+p-1-i,r-1))}
%o 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
%Y Cf. A007297, A143018.
%K nonn
%O 2,2
%A _Emeric Deutsch_, Jul 30 2008
|
