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

Author

Emeric Deutsch

Keywords

• nonn
• easy

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

Examples

			From _Alexander Burstein_, Feb 14 2025: (Start)
a(2) = 4 as the maximum number of distinct sets obtained as complete parenthesizations of S_1 u(nion) S_2 (i)n(tersect) S_3 u(nion) S_4:
S_1 u (S_2 n (S_3 u S_4)),
S_1 u ((S_2 n S_3) u S_4) = (S_1 u (S_2 n S_3)) u S_4,
(S_1 u S_2) n (S_3 u S_4),
((S_1 u S_2) n S_3) u S_4. (End)
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..950
• Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.
• Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See pp. 7, 11.

Crossrefs

Convolution of A027307 with itself.

Cf. A060628 diagonal(-6).

Programs

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

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

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)