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!)
A003169 Number of 2-line arrays; or number of P-graphs with 2n edges.
(Formerly M2973)
17

%I M2973 #72 Jun 13 2023 03:33:32

%S 1,3,14,79,494,3294,22952,165127,1217270,9146746,69799476,539464358,

%T 4214095612,33218794236,263908187100,2110912146295,16985386737830,

%U 137394914285538,1116622717709012,9113225693455362,74659999210200292

%N Number of 2-line arrays; or number of P-graphs with 2n edges.

%C First column of triangle A100326. - _Paul D. Hanna_, Nov 16 2004

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A003169/b003169.txt">Table of n, a(n) for n = 1..200</a>

%H M. Bicknell and V. E. Hoggatt, Jr., <a href="http://www.fq.math.ca/Scanned/14-3/hoggatt1.pdf">Sequences of matrix inverses from Pascal, Catalan and related convolution arrays</a>, Fib. Quart., 14 (1976), 224-232.

%H L. Carlitz, <a href="http://www.fq.math.ca/Scanned/11-2/carlitz.pdf">Enumeration of two-line arrays</a>, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=416">Encyclopedia of Combinatorial Structures 416</a>

%H R. C. Read, <a href="http://dx.doi.org/10.1007/BF02188172">On the enumeration of a class of plane multigraphs</a>, Aequat. Math. 31 (1986) no 1, 47-63.

%H Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, <a href="https://arxiv.org/abs/1706.03357">Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing</a>, arXiv:1706.03357 [cs.CL], 2017.

%F For formula see Read reference.

%F D-finite with recurrence a(n) = ( (324*n^2-708*n+360)*a(n-1) - (371*n^2-1831*n+2250)*a(n-2) + (20*n^2-130*n+210)*a(n-3) )/(16*n*(2*n-1)) for n>2, with a(0)=0, a(1)=1, a(2)=3. - _Paul D. Hanna_, Nov 16 2004

%F G.f. satisfies: A(x) = x*(1+A(x))/(1-A(x))^2 where A(0)=0. G.f. satisfies: (1+A(x))/(1-A(x)) = 2*G003168(x)-1, where G003168 is the g.f. of A003168. - _Paul D. Hanna_, Nov 16 2004

%F a(n) = (1/n)*Sum_{i=0..n-1} binomial(n,i)*binomial(3*n-i-2,n-i-1). - _Vladeta Jovovic_, Sep 13 2006

%F Appears to be (1/n)*Jacobi_P(n-1,1,n-1,3). If so then a(n) = (1/(2*n-1))*Sum_{k = 0..n-1} binomial(n-1,k)*binomial(2*n+k-1,k+1) = (1/n)*Sum_{k = 0..n} binomial(n,k)*binomial(2*n-2,n+k-1)*2^k. [Added Jun 11 2023: these are correct, and can be proved using the WZ algorithm.] - _Peter Bala_, Aug 01 2012

%F a(n) ~ sqrt(33/sqrt(17)-7) * ((71+17*sqrt(17))/16)^n / (4*sqrt(2*Pi)*n^(3/2)). - _Vaclav Kotesovec_, Aug 09 2013

%F The o.g.f. A(x) = 1 + 3*x + 14*x^2 + ... taken with offset 0, satisfies 1 + x*A'(x)/A(x) = 1 + 3*x + 19*x^2 + 138*x^3 + ..., the o.g.f. for A156894. - _Peter Bala_, Oct 05 2015

%F From _Peter Bala_, Jun 11 2023: (Start)

%F a(n) = (1/n)*Sum_{k = 0..n-1} binomial(n,k+1)*binomial(2*n+k-1,k) (Carlitz, equation 3.19).

%F 4*n*(17*n - 29)*(2*n - 1)*a(n) = (1207*n^3 - 4473*n^2 + 5258*n - 1920)*a(n-1) - 2*(2*n - 5)*(17*n - 12)*(n - 2)*a(n-2) with a(1) = 1 and a(2) = 3. (End)

%p a[0]:=0:a[1]:=1:a[2]:=3:for n from 3 to 30 do a[n]:=((324*n^2-708*n+360)*a[n-1] -(371*n^2-1831*n+2250)*a[n-2]+(20*n^2-130*n+210)*a[n-3])/(16*n*(2*n-1)) od:seq(a[n],n=1..25); # _Emeric Deutsch_, Jan 31 2005

%t lim = 21; t[0, 0] = 1; t[n_, 0] := t[n, 0] = Sum[(k + 1)*t[n - 1, k], {k, 0, n - 1}]; t[n_, k_] := t[n, k] = Sum[t[j + 1, 0]*t[n - j - 1, k - 1], {j, 0, n - k}]; Table[ t[n, 0], {n, lim}] (* _Jean-François Alcover_, Sep 20 2011, after _Paul D. Hanna_'s comment *)

%o (PARI) {a(n)=if(n==0,0,if(n==1,1,if(n==2,3,( (324*n^2-708*n+360)*a(n-1) -(371*n^2-1831*n+2250)*a(n-2)+(20*n^2-130*n+210)*a(n-3))/(16*n*(2*n-1)) )))} \\ _Paul D. Hanna_, Nov 16 2004

%o (PARI) {a(n)=local(A=x+x*O(x^n));if(n==1,1, for(i=1,n,A=x*(1+A)/(1-A)^2); polcoeff(A,n))}

%o (PARI) seq(n)=Vec(serreverse(x*(1 - x)^2/(1 + x) + O(x*x^n))) \\ _Andrew Howroyd_, Mar 07 2023

%o (Haskell)

%o a003169 = flip a100326 0 -- _Reinhard Zumkeller_, Nov 21 2015

%Y Cf. A003168, A100324, A100326, A156894.

%K nonn,easy

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Emeric Deutsch_, Jan 31 2005

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 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)