A032349 Number of paths from (0,0) to (3n,0) that stay in first quadrant (but may touch horizontal axis), where each step is (2,1),(1,2) or (1,-1) and start with (2,1).

1, 4, 24, 172, 1360, 11444, 100520, 911068, 8457504, 80006116, 768464312, 7474561164, 73473471344, 728745517972, 7284188537672, 73301177482172, 742009157612608, 7550599410874820, 77193497566719320, 792498588659426924

Offset

1,2

Comments

a(n) is the maximum number of distinct sets that can be obtained as complete parenthesizations of “S_1 union S_2 intersect S_3 union S_4 intersect S_5 union ... union S_{2*n}”, where n union and n-1 intersection operations alternate, starting with a union, and S_1, S_2, ... , S_{2*n} are sets. - Alexander Burstein, Nov 22 2023

Links

G. C. Greubel, Table of n, a(n) for n = 1..950

Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.

Formula

G.f.: z*A^2, where A is the g.f. of A027307.

a(n) = 2*Sum_{i=0..n-1} (2*n+i-1)!/(i!*(n-i-1)!*(n+i+1)!). - Vladimir Kruchinin, Oct 18 2011

D-finite with recurrence: n*(2*n-1)*a(n) = (28*n^2-65*n+36)*a(n-1) - (64*n^2-323*n+408)*a(n-2) - 3*(n-4)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 08 2012

a(n) ~ sqrt(45*sqrt(5)-100)*((11+5*sqrt(5))/2)^n/(5*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 08 2012

G.f. A(x) satisfies: A(x) = 1 + x * ( A(x) + sqrt(A(x)) )^2. - Paul D. Hanna, Jun 11 2016

From Peter Bala, May 07 2023: (Start)

n*(2*n-1)*(5*n-9)*a(n) = 2*(55*n^3-209*n^2+255*n-99)*a(n-1) + (n-3)*(2*n-3)*(5*n-4)*a(n-2) with a(1) = 1 and a(2) = 4.

G.f.: A(x) = series reversion of x*(1 - x)^2/(1 + x)^2. (End)

Mathematica

RecurrenceTable[{n*(2*n-1)*a[n] == (28*n^2-65*n+36)*a[n-1] - (64*n^2-323*n+408)*a[n-2] - 3*(n-4)*(2*n-5)*a[n-3], a[1]==1, a[2]==4, a[3]==24}, a, {n, 20}] (* Vaclav Kotesovec, Oct 08 2012 *)

Prog

(Maxima)
a(n):=2*sum((2*n+i-1)!/(i!*(n-i-1)!*(n+i+1)!), i, 0, n-1); \\ Vladimir Kruchinin, Oct 18 2011
(PARI) vector(30, n, 2*sum(k=0, n-1, (2*n+k-1)!/(k!*(n-k-1)!*(n+k+1)!))) \\ Altug Alkan, Oct 06 2015
(PARI) {a(n) = my(A=1); for(i=1, n, A = 1 + x*(A + sqrt(A +x*O(x^n)))^2); polcoeff(A, n)}
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Jun 11 2016

Crossrefs

Convolution of A027307 with itself.

Cf. A060628 diagonal(-6).

Sequence in context: A366980 A369471 A347651 * A215709 A103334 A156017

Adjacent sequences: A032346 A032347 A032348 * A032350 A032351 A032352

Keyword

nonn,easy

Author

Emeric Deutsch

Status

approved