cp's OEIS Frontend

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

%I A032349 #55 Feb 23 2025 11:25:33
%S A032349 1,4,24,172,1360,11444,100520,911068,8457504,80006116,768464312,
%T A032349 7474561164,73473471344,728745517972,7284188537672,73301177482172,
%U A032349 742009157612608,7550599410874820,77193497566719320,792498588659426924
%N 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).
%C A032349 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
%H A032349 G. C. Greubel, <a href="/A032349/b032349.txt">Table of n, a(n) for n = 1..950</a>
%H A032349 Emeric Deutsch, <a href="http://www.jstor.org/stable/2589192">Problem 10658</a>, American Math. Monthly, 107, 2000, 368-370.
%H A032349 Jun Yan, <a href="https://arxiv.org/abs/2501.01152">Lattice paths enumerations weighted by ascent lengths</a>, arXiv:2501.01152 [math.CO], 2025. See pp. 7, 11.
%F A032349 G.f.: z*A^2, where A is the g.f. of A027307.
%F A032349 a(n) = 2*Sum_{i=0..n-1} (2*n+i-1)!/(i!*(n-i-1)!*(n+i+1)!). - _Vladimir Kruchinin_, Oct 18 2011
%F A032349 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
%F A032349 a(n) ~ sqrt(45*sqrt(5)-100)*((11+5*sqrt(5))/2)^n/(5*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 08 2012
%F A032349 G.f. A(x) satisfies: A(x) = 1 + x * ( A(x) + sqrt(A(x)) )^2. - _Paul D. Hanna_, Jun 11 2016
%F A032349 From _Peter Bala_, May 07 2023: (Start)
%F A032349 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.
%F A032349 G.f.: A(x) = series reversion of x*(1 - x)^2/(1 + x)^2. (End)
%e A032349 From _Alexander Burstein_, Feb 14 2025: (Start)
%e A032349 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:
%e A032349 S_1 u (S_2 n (S_3 u S_4)),
%e A032349 S_1 u ((S_2 n S_3) u S_4) = (S_1 u (S_2 n S_3)) u S_4,
%e A032349 (S_1 u S_2) n (S_3 u S_4),
%e A032349 ((S_1 u S_2) n S_3) u S_4. (End)
%t A032349 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 *)
%o A032349 (Maxima)
%o A032349 a(n):=2*sum((2*n+i-1)!/(i!*(n-i-1)!*(n+i+1)!),i,0,n-1); /* _Vladimir Kruchinin_, Oct 18 2011 */
%o A032349 (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
%o A032349 (PARI) {a(n) = my(A=1); for(i=1,n, A = 1 + x*(A + sqrt(A +x*O(x^n)))^2); polcoeff(A,n)}
%o A032349 for(n=0,30, print1(a(n),", ")) \\ _Paul D. Hanna_, Jun 11 2016
%Y A032349 Convolution of A027307 with itself.
%Y A032349 Cf. A060628 diagonal(-6).
%K A032349 nonn,easy
%O A032349 1,2
%A A032349 _Emeric Deutsch_