A027307 -id:A027307 - cp's OEIS frontend

A107708 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (x,y >= 0) and where each step is (3,0), (2,1), (1,2), or (1,-1).

1, 3, 18, 144, 1323, 13176, 138348, 1507977, 16900650, 193536864, 2254630788, 26635735440, 318350663748, 3842488208997, 46770206742342, 573435609537600, 7075551692662875, 87794803094586336, 1094807464312435344

Offset: 0

Emeric Deutsch, Jun 10 2005

nonn

			a(1)=3 because we have H, uD and Udd, where H=(3,0), u=(2,1), U=(1,2) and D=(1,-1).

G. C. Greubel, Table of n, a(n) for n = 0..880
Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.
M. Dziemianczuk, Counting Lattice Paths With Four Types of Steps, Graphs and Combinatorics, September 2013, DOI 10.1007/s00373-013-1357-1.

Cf. A027307, A106228, A346626.

a:=n->(1/n)*sum(3^j*binomial(n,j)*binomial(n+j,2*n+1-j),j=ceil((n+1)/2)..n): 1,seq(a(n),n=1..22);

Flatten[{1,Table[1/n*Sum[3^j*Binomial[n, j]*Binomial[n+j, 2n+1-j], {j,Floor[(n+1)/2],n}],{n,1,20}]}] (* Vaclav Kotesovec, Mar 17 2014 *)

concat([1], for(n=1,50, print1((1/n)*sum(j=floor((n+1)/2),n, 3^j*binomial(n,j)*binomial(n+j,2*n+1-j)), ", "))) \\ G. C. Greubel, Mar 16 2017

a(n) = (1/n)*Sum(3^j*binomial(n, j)*binomial(n+j, 2n+1-j), j=ceiling((n+1)/2)..n) for n >= 1; a(0)=1.
G.f. = (2/3)w*sin((1/3)*arcsin((36-7z)/2/(3-2z)/w))-1/3, where w=sqrt((3-2z)/z).
Recurrence: 2*n*(2*n+1)*(17*n-25)*a(n) = 4*(238*n^3 - 588*n^2 + 395*n - 72)*a(n-1) - 12*(n-2)*(34*n^2 - 67*n + 21)*a(n-2) + 3*(n-3)*(n-2)*(17*n - 8)*a(n-3). - Vaclav Kotesovec, Mar 17 2014
a(n) ~ (1/204)*sqrt(102)*sqrt((134963 + 21573*sqrt(17))^(1/3) * ((134963 + 21573*sqrt(17))^(2/3) + 2176 + 68*(134963 + 21573*sqrt(17))^(1/3))) / ((134963 + 21573*sqrt(17))^(1/3)*sqrt(Pi)) * 6^(-n) * ((19009 + 153*sqrt(17))^(2/3) + 712 + 28*(19009 + 153*sqrt(17))^(1/3))^n * (19009 + 153*sqrt(17))^(-n/3)*(1/n)^(3/2). - Vaclav Kotesovec, Mar 17 2014
D-finite with recurrence 8*n*(2*n+1)*a(n) +2*(-106*n^2+97*n-18)*a(n-1) +36*(-2*n^2+12*n-15)*a(n-2) +12*(5*n-14)*(n-3)*a(n-3) -9*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jul 26 2022
G.f. satisfies A(x) = 1 + x * A(x) * (1 + A(x) + A(x)^2). - Seiichi Manyama, Apr 01 2024

A108425 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have k peaks (i.e., ud and Ud's).

Original entry on oeis.org

2, 4, 6, 8, 36, 22, 16, 144, 248, 90, 32, 480, 1600, 1560, 394, 64, 1440, 7840, 14400, 9420, 1806, 128, 4032, 32480, 95760, 115416, 55692, 8558, 256, 10752, 120064, 517440, 986272, 860832, 325360, 41586, 512, 27648, 408576, 2419200, 6668928

Offset: 1

Emeric Deutsch, Jun 03 2005

Row sums yield A027307. T(n,n) = A006318(n) (the large Schroeder numbers; asks for a bijective proof). T(n,1) = 2^n.

			Example T(2,1)=4 because we have uudd, uUddd, Uuddd and UUdddd.
Triangle begins:
   2;
   4,   6;
   8,  36,  22;
  16, 144, 248,  90;

Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150).
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.

Cf. A006318, A027307, A108426.

T:=(n,k)->(1/n)*binomial(n,k)*sum(2^(n-j)*binomial(n,j)*binomial(n,k-1-j),j=0..k-1): for n from 1 to 10 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

Table[(1/n) Binomial[n, k] Sum[2^(n - j) Binomial[n, j] Binomial[n, k - 1 - j], {j, 0, k - 1}], {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, Oct 06 2015 *)

T(n, k) = (1/n)binomial(n, k)*Sum_{j=0..k-1} 2^(n-j)*binomial(n, j)*binomial(n, k-1-j).

G.f.: G = G(t, z) satisfies zG^3 + tzG^2 - (1 + z - tz)G + 1 = 0.

A108431 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have k hills (a hill is either a ud or a Udd starting at the x-axis).

Original entry on oeis.org

1, 0, 2, 6, 0, 4, 34, 24, 0, 8, 274, 136, 72, 0, 16, 2266, 1168, 408, 192, 0, 32, 19738, 9880, 3720, 1088, 480, 0, 64, 177642, 87840, 32088, 10496, 2720, 1152, 0, 128, 1640050, 802216, 291048, 92096, 27680, 6528, 2688, 0, 256, 15445690, 7492240

Offset: 0

Emeric Deutsch, Jun 03 2005

Row sums yield A027307. T(n,0) = A108432(n). T(n,n) = 2^n.

			Example T(2,2)=4 because we have udud, udUdd, Uddud and UddUdd.
Triangle begins:
1;
0,2;
6,0,4;
34,24,0,8;
...

Alois P. Heinz, Rows n = 0..140, flattened
Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Cf. A027307, A108432, A108433.

A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3: G:=1/(1-z*A+2*z-2*z*t-z*A^2): Gserz:=simplify(series(G,z=0,12)): P[0]:=1: for n from 1 to 10 do P[n]:=sort(coeff(Gserz,z^n)) od: for n from 0 to 9 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(y<0 or y>x, 0,
     `if`(x=0, 1, b(x-1, y-1, t)*`if`(t and y=1, z, 1)+
      b(x-1, y+2, is(y=0))+b(x-2, y+1, is(y=0)))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..n))(b(3*n, 0, false)):
seq(T(n), n=0..10);  # Alois P. Heinz, Oct 06 2015

b[x_, y_, t_] := b[x, y, t] = Expand[If[y<0 || y>x, 0, If[x == 0, 1, b[x-1, y-1, t]*If[t && y == 1, z, 1] + b[x-1, y+2, y == 0] + b[x-2, y+1, y == 0]]]]; T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, n}]][b[ 3*n, 0, False]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 25 2015, after Alois P. Heinz *)

G.f.: 1/(1-2tz+2z-zA-zA^2), where A=1+zA^2+zA^3 or, equivalently, A=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).

A108432 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have no hills (a hill is either a ud or a Udd starting at the x-axis).

Original entry on oeis.org

1, 0, 6, 34, 274, 2266, 19738, 177642, 1640050, 15445690, 147813706, 1433309194, 14052298690, 139063589370, 1387288675002, 13936344557354, 140859338668306, 1431424362057018, 14616361066692778, 149892742974500042, 1543146417012350050, 15942622531081651578

Offset: 0

Emeric Deutsch, Jun 03 2005

Column 0 of A108431.

The radius of convergence of g.f. y(x) is r = (5*sqrt(5)-11)/2, with y(r) = (11*sqrt(5)+23)/38. - Vaclav Kotesovec, Mar 17 2014

			a(2)=6 because we have uudd, uUddd, Ududd, UdUddd, Uuddd and UUdddd.

Alois P. Heinz, Table of n, a(n) for n = 0..960 (first 151 terms from Vaclav Kotesovec)
Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Cf. A027307, A108431, A108433.

g:=1/(1+2*z-z*A-z*A^2): A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3:gser:=series(g,z=0,27): 1,seq(coeff(gser,z^n),n=1..24);
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, `if`(t and y=1, 0, b(x-1, y-1, t))+
      b(x-1, y+2, is(y=0))+b(x-2, y+1, is(y=0))))
    end:
a:= n-> b(3*n, 0, false):
seq(a(n), n=0..25);  # Alois P. Heinz, Oct 06 2015

CoefficientList[Series[9/(3 + 18*x + 2*(3+x)*Cos[2/3*ArcSin[Sqrt[x]*(18+x)/(3+x)^(3/2)]] - 2*x*Sqrt[(3+x)/x]*Sin[1/3*ArcSin[Sqrt[x]*(18+x)/(3+x)^(3/2)]]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 17 2014 *)

{a(n)=local(y=1); for(i=1, n, y=-(-1 + 6*x*y - 5*x*y^2 - 12*x^2*y^2 - x*y^3 + 6*x^2*y^3 + 8*x^3*y^3) + (O(x^n))^3); polcoeff(y, n)}
for(n=0, 20, print1(a(n), ", ")) \\ Vaclav Kotesovec, Mar 17 2014

G.f.: 1/(1+2z-zA-zA^2), where A=1+zA^2+zA^3 or, equivalently, A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).
G.f. y(x) satisfies: -1 + y + 6*x*y - 5*x*y^2 - 12*x^2*y^2 - x*y^3 + 6*x^2*y^3 + 8*x^3*y^3 = 0. - Vaclav Kotesovec, Mar 17 2014
a(n) ~ (11+5*sqrt(5))^n * sqrt(273965 + 122523*sqrt(5)) / (361 * sqrt(5*Pi) * n^(3/2) * 2^(n+3/2)). - Vaclav Kotesovec, Mar 17 2014
D-finite with recurrence 4*n*(2*n+1)*a(n) +3*(-70*n^2+83*n-34)*a(n-1) +11*(154*n^2-436*n+327)*a(n-2) +3*(-1042*n^2+4875*n-4627)*a(n-3) +2*(-4016*n^2+18260*n-21399)*a(n-4) +12*(-206*n^2+1383*n-2322)*a(n-5) -80*(n-4)*(2*n-9)*a(n-6)=0. - R. J. Mathar, Jul 26 2022

A108433 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1) and have k hills of the form ud (a hill is either a ud or a Udd starting at the x-axis).

Original entry on oeis.org

1, 1, 1, 7, 2, 1, 47, 15, 3, 1, 361, 108, 24, 4, 1, 2977, 865, 184, 34, 5, 1, 25775, 7334, 1533, 276, 45, 6, 1, 231103, 64767, 13359, 2387, 385, 57, 7, 1, 2127409, 589368, 120376, 21368, 3450, 512, 70, 8, 1, 19990241, 5488033, 1112424, 196484, 31706

Offset: 0

Emeric Deutsch, Jun 03 2005

Row sums yield A027307. T(n,0)=A108434(n). A027307, A108432, A108433, A108434.

			Example T(2,1)=2 because we have udUdd and Uddud.
Triangle begins:
1;
1,1;
7,2,1;
47,15,3,1;
361,108,24,4,1;

Alois P. Heinz, Rows n = 0..140, flattened
Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Cf. A027307, A108431, A108432, A108434.

A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3: G:=1/(1-z*A+z-t*z-z*A^2): Gserz:=simplify(series(G,z=0,12)): P[0]:=1: for n from 1 to 10 do P[n]:=sort(coeff(Gserz,z^n)) od: for n from 0 to 9 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(y<0 or y>x, 0,
     `if`(x=0, 1, b(x-1, y-1, t)*`if`(t and y=1, z, 1)+
      b(x-1, y+2, false)+b(x-2, y+1, is(y=0)))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..n))(b(3*n, 0, false)):
seq(T(n), n=0..10);  # Alois P. Heinz, Oct 06 2015

b[x_, y_, t_] := b[x, y, t] = Expand[If[y < 0 || y > x, 0, If[x == 0, 1, b[x - 1, y - 1, t]*If[t && y == 1, z, 1] + b[x - 1, y + 2, False] + b[x - 2, y + 1, y == 0]]]]; T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, n}]][b[3*n, 0, False]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 29 2016, after Alois P. Heinz *)

G.f.: 1/(1-tz+z-zA-zA^2), where A=1+zA^2+zA^3 or, equivalently, A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).

A108445 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have k pyramids (a pyramid is a sequence u^pd^p or U^pd^(2p) for some positive integer p, starting at the x-axis).

Original entry on oeis.org

1, 0, 2, 4, 2, 4, 32, 18, 8, 8, 252, 146, 60, 24, 16, 2112, 1186, 496, 176, 64, 32, 18484, 10146, 4148, 1488, 480, 160, 64, 166976, 90162, 36216, 12792, 4160, 1248, 384, 128, 1545548, 824114, 326828, 113960, 36720, 11104, 3136, 896, 256, 14583808, 7699394

Offset: 0

Emeric Deutsch, Jun 11 2005

Row sums yield A027307. Column 0 yields A108449. Number of pyramids in all paths from (0,0) to (3n,0) is given by A108450

			T(2,1)=2 because we have uudd and UUdddd.
Triangle begins:
1;
0,2;
4,2,4;
32,18,8,8;
252,146,60,24,16;

Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Cf. A027307, A108449, A108450.

A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3: G:=(1-z)/(1+z-2*t*z-z*(1-z)*A*(1+A)): Gser:=simplify(series(G,z=0,12)): P[0]:=1: for n from 1 to 9 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 9 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields sequence in triangular form

G.f. =(1-z)/[1+z-2tz-z(1-z)A(1+A)], where A=1+zA^2+zA^3=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).

A108449 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and having no pyramids (a pyramid is a sequence u^pd^p or U^pd^(2p) for some positive integer p, starting at the x-axis).

Original entry on oeis.org

1, 0, 4, 32, 252, 2112, 18484, 166976, 1545548, 14583808, 139774180, 1356966240, 13316740764, 131890671680, 1316627340564, 13234192747648, 133829733962732, 1360586260341248, 13898403178004420, 142578916276009632

Offset: 0

Emeric Deutsch, Jun 11 2005

nonn

Column 0 of A108445.

			a(2)=4 because the paths uUddd, Ududd, UdUddd and Uuddd have no pyramids.

Vaclav Kotesovec, Table of n, a(n) for n = 0..100
Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Cf. A027307, A108445.

A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3: g:=(1-z)/(1+z-z*(1-z)*A*(1+A)): gser:=series(g,z=0,24): 1,seq(coeff(gser,z^n),n=1..21);

{a(n)=local(y=1); for(i=1, n, y = -(-1 + 3*x - 3*x^2 + x^3 + 3*x*y - 9*x^2*y + 5*x^3*y - 5*x*y^2 - x^2*y^2 + 5*x^3*y^2 + x^4*y^2 - x*y^3 + 9*x^2*y^3 - 3*x^3*y^3 + 3*x^4*y^3) + (O(x^n))^4); polcoeff(y, n)}
for(n=0, 20, print1(a(n), ", ")) \\ Vaclav Kotesovec, Mar 18 2014

G.f.=(1-z)/[1+z-z(1-z)A(1+A)], where A=1+zA^2+zA^3=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).
G.f. y(x) satisfies: -1 + 3*x - 3*x^2 + x^3 + y + 3*x*y - 9*x^2*y + 5*x^3*y - 5*x*y^2 - x^2*y^2 + 5*x^3*y^2 + x^4*y^2 - x*y^3 + 9*x^2*y^3 - 3*x^3*y^3 + 3*x^4*y^3 = 0. - Vaclav Kotesovec, Mar 18 2014
a(n) ~ (11+5*sqrt(5))^n * sqrt(1738885 + 811683*sqrt(5)) / (961*sqrt(5*Pi) *n^(3/2)*2^(n+3/2)). - Vaclav Kotesovec, Mar 18 2014
Conjecture D-finite with recurrence +n*(2*n+1)*(431*n-2895)*a(n) +2*(-9395*n^3+68622*n^2-64084*n+26109)*a(n-1) +2*(59288*n^3-508196*n^2+1044822*n-574587)*a(n-2) +2*(-94965*n^3+1070605*n^2-3607435*n+3485484)*a(n-3) +4*(29036*n^3-351474*n^2+1402336*n-1970505)*a(n-4) +6*(-6703*n^3+63052*n^2-99178*n-237177)*a(n-5) +6*(1012*n^3-14914*n^2+74580*n-127341)*a(n-6) +6*(1127*n^3-21429*n^2+135199*n-282762
)*a(n-7) +9*(29*n-165)*(2*n-15)*(n-8)*a(n-8)=0. - R. J. Mathar, Jul 26 2022

A363305 Expansion of g.f. A(x) satisfying A(x) = 1 + x*(A(x)^5 + A(x)^9).

Original entry on oeis.org

1, 2, 28, 576, 13968, 371280, 10465152, 307252032, 9295409664, 287758274304, 9071667965184, 290237226038272, 9399819302979584, 307570021821937664, 10152439243763290112, 337658352835320934400, 11304320019217804476416, 380650592731460987617280

Offset: 0

Paul D. Hanna, May 29 2023

nonn

			G.f.: A(x) = 1 + 2*x + 28*x^2 + 576*x^3 + 13968*x^4 + 371280*x^5 + 10465152*x^6 + 307252032*x^7 + 9295409664*x^8 + ...
where A(x) = 1 + x*(A(x)^5 + A(x)^9).
RELATED SERIES.
A(x)^5 = 1 + 10*x + 180*x^2 + 4080*x^3 + 104160*x^4 + 2858352*x^5 + 82336320*x^6 + 2455727040*x^7 + ...
A(x)^9 = 1 + 18*x + 396*x^2 + 9888*x^3 + 267120*x^4 + 7606800*x^5 + 224915712*x^6 + 6839682624*x^7 + ...

Seiichi Manyama, Table of n, a(n) for n = 0..500

Cf. A027307, A363311, A363304.

{a(n) = sum(k=0, n, binomial(n, k)*binomial(5*n+4*k+1, n)/(5*n+4*k+1) )}
for(n=0, 20, print1(a(n), ", "))

G.f.: A(x) = Sum_{n>=0} a(n)*x^n may be defined by the following.
(1) A(x) = 1 + x*(A(x)^5 + A(x)^9).
(2) a(n) = Sum_{k=0..n} binomial(n, k)*binomial(5*n+4*k+1, n)/(5*n+4*k+1) for n >= 0.

A033296 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 (1,2).

Original entry on oeis.org

1, 1, 6, 42, 326, 2706, 23526, 211546, 1951494, 18366882, 175674054, 1702686090, 16686795846, 165079509042, 1646340228006, 16534463822010, 167081444125702, 1697551974416706, 17330661859937670, 177699201786231530

Offset: 0

Emeric Deutsch

nonn

			G.f. A(x) = 1 + x + 6*x^2 + 42*x^3 + 326*x^4 + 2706*x^5 + 23526*x^6 + 211546*x^7 + 1951494*x^8 + 18366882*x^9 + 175674054*x^10 + ...

Cf. A027307, A032349, A363308.

/* G.f. A(x) = (1/x)*Series_Reversion( x/C(x*C(x)^3) ) */
{a(n) = my(C = (1 - sqrt(1 - 4*x +x^2*O(x^n)))/(2*x)); polcoeff( (1/x)*serreverse(x/subst(C,x,x*C^3)), n)}
for(n=0,20,print1(a(n),", ")) \\ Paul D. Hanna, May 28 2023

G.f.: A(x) = 1 + x*D(x)^3, where D(x) is the g.f. of A027307. Also: difference of A027307 and A032349. [Changed formula to include a(0) = 1. - Paul D. Hanna, May 28 2023]
D-finite with recurrence +n*(2*n+1)*a(n) +(-32*n^2+47*n-17)*a(n-1) +2*(55*n^2-223*n+228)*a(n-2) +3*(-4*n^2+33*n-70)*a(n-3) -(2*n-7)*(n-5)*a(n-4)=0. - R. J. Mathar, Jul 24 2022
From Paul D. Hanna, May 28 2023: (Start)
G.f. A(x) = (1/x) * Series_Reversion( x / C(x*C(x)^3) ), where C(x) = 1 + x*C(x)^2 is the g.f. of the Catalan numbers (A000108).
G.f. A(x) = B(x*A(x)) where B(x) = A(x/B(x)) = C(x*C(x)^3) is the g.f. of A363308, and C(x) is the g.f. of the Catalan numbers (A000108). (End)

A108427 Number of peaks of the form Ud in all paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1).

Original entry on oeis.org

1, 9, 85, 833, 8361, 85305, 880685, 9173505, 96220561, 1014889769, 10753517061, 114375683009, 1220435354425, 13058529727833, 140059477112925, 1505357362548737, 16209464357137953, 174827809500822345, 1888383038494338485, 20424130116241366593, 221164921352046545609, 2397512484385887298681

Offset: 1

Emeric Deutsch, Jun 03 2005

nonn

			a(2)=9 because we have ud(Ud)d, u(Ud)dd, (Ud)dud, (Ud)d(Ud)d, (Ud)udd, (Ud)(Ud)dd, U(Ud)ddd (the peaks of the form Ud shown between parentheses).
G.f. = x + 9*x^2 + 85*x^3 + 833*x^4 + 8361*x^5 + 85305*x^6 + 880685*x^7 + ... - _Michael Somos_, Jul 01 2018

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.

Cf. A027307, A108426.

seq(add(k*binomial(n,k)*binomial(3*n-k,n-1)/n,k=0..n),n=1..22);
a := n -> binomial(3*n-1,n-1)*hypergeom([1-n,-2*n], [1-3* n], -1); seq(round(evalf(a(n),32)), n=1..22); # Peter Luschny, Oct 06 2015

Table[1/n*Sum[k*Binomial[n, k]*Binomial[3n - k, n-1], {k, 0, n}], {n, 1, 20}] (* Vaclav Kotesovec, Oct 17 2012 *)
a[n_] :=  HypergeometricPFQ[{-n, n, -n + 1}, {1/2, 1}, 1];
Table[a[n], {n, 1, 22}] (* Peter Luschny, Mar 14 2018 *)
a[ n_] := JacobiP[n - 1, n + 1, 0, 3]; (* Michael Somos, Jul 01 2018 *)

G(z):=z*((2/3)*sqrt((z+3)/z)*sin((1/3)*asin(sqrt(z)*(z+18) / (z+3)^(3/2)))+2/3);
taylor(diff(G(z),z,1)/G(z)-1/z,z,0,20); /* Vladimir Kruchinin, Oct 06 2015 */

a(n) = (1/n)*sum(k=0,n,k*binomial(n, k)*binomial(3*n-k, n-1)); \\ Joerg Arndt, May 15 2013

a(n) = (1/n)*Sum_{k=0..n} k*binomial(n, k)*binomial(3n-k, n-1).
Recurrence: 9*n*(2*n-3)*a(n) = (202*n^2 - 414*n + 185)*a(n-1) - (26*n^2 - 175*n + 255)*a(n-2) - 2*(n-3)*(2*n-5)*a(n-3), for n>3. - Vaclav Kotesovec, Oct 17 2012
a(n) ~ sqrt(30*sqrt(5)-50)*((11+5*sqrt(5))/2)^n/(20*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 17 2012. Equivalently, a(n) ~ phi^(5*n - 1) / (2* 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021
G.f.: A(x) = 1/2*(x*B'(x)/B(x)-1), where B(x) satisfies B(x) = x*((1-2*B(x))/(2*(1-4*B(x))) + 1/(2*sqrt(1-4*B(x)))). - Vladimir Kruchinin, Oct 06 2015
a(n) = binomial(3*n-1, n-1)*hypergeom([1-n, -2*n], [1-3*n], -1). - Peter Luschny, Oct 06 2015
a(n) = hypergeom([-n, n, -n + 1], [1/2,  1], 1). - Peter Luschny, Mar 14 2018
a(n) = P(n-1, n+1, 0, 3), where P is the Jacobi Polynomial. - Richard Turk, Jun 25 2018

cp's OEIS Frontend

A107708 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (x,y >= 0) and where each step is (3,0), (2,1), (1,2), or (1,-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A108425 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have k peaks (i.e., ud and Ud's).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A108431 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have k hills (a hill is either a ud or a Udd starting at the x-axis).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A108432 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have no hills (a hill is either a ud or a Udd starting at the x-axis).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A108433 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1) and have k hills of the form ud (a hill is either a ud or a Udd starting at the x-axis).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A108449 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and having no pyramids (a pyramid is a sequence u^pd^p or U^pd^(2p) for some positive integer p, starting at the x-axis).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs