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

1, 3, 14, 79, 494, 3294, 22952, 165127, 1217270, 9146746, 69799476, 539464358, 4214095612, 33218794236, 263908187100, 2110912146295, 16985386737830, 137394914285538, 1116622717709012, 9113225693455362, 74659999210200292

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

First column of triangle A100326. - Paul D. Hanna, Nov 16 2004

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..200
• M. Bicknell and V. E. Hoggatt, Jr., Sequences of matrix inverses from Pascal, Catalan and related convolution arrays, Fib. Quart., 14 (1976), 224-232.
• L. Carlitz, Enumeration of two-line arrays, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 416
• R. C. Read, On the enumeration of a class of plane multigraphs, Aequat. Math. 31 (1986) no 1, 47-63.
• Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See p. 8.
• Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing, arXiv:1706.03357 [cs.CL], 2017.

Crossrefs

Cf. A003168, A100324, A100326, A156894.

Programs

Haskell

a003169 = flip a100326 0  -- Reinhard Zumkeller, Nov 21 2015

Maple

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

Mathematica

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 *)

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

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))}

PARI

seq(n)=Vec(serreverse(x*(1 - x)^2/(1 + x) + O(x*x^n))) \\ Andrew Howroyd, Mar 07 2023

Formula

For formula see Read reference.

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

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

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

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

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

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

From Peter Bala, Jun 11 2023: (Start)

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

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)

Extensions

More terms from Emeric Deutsch, Jan 31 2005