A108446 -id:A108446 - cp's OEIS frontend

A108447 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 peaks of the form ud.

1, 1, 4, 20, 113, 688, 4404, 29219, 199140, 1385904, 9807820, 70364704, 510609620, 3741212535, 27639233548, 205660399220, 1539916433473, 11594310041792, 87725707127600, 666681174728724, 5086601816592432, 38948589882247968

Offset: 0

Emeric Deutsch, Jun 10 2005

nonn

Column 0 of A108446.

			a(2)=4 because we have uUddd, UddUdd, UdUddd and UUdddd.

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

Cf. A000108, A027307, A108446, A108425, A108426.

a:=n->(1/n)*sum(binomial(n,j)*binomial(n+2*j,j-1),j=0..n): 1, seq(a(n),n=1..25);
a := n -> `if`(n=0,1,simplify(hypergeom([1-n,(n+3)/2,(n+4)/2],[2, n+3],-4))): seq(a(n), n=0..21); # Peter Luschny, Oct 30 2015

Flatten[{1, Table[Sum[Binomial[n, j]*Binomial[n + 2*j, j-1], {j, 0, n}]/n, {n, 1, 20}]}] (* Vaclav Kotesovec, Nov 27 2017 *)
terms = 22; g[] = 1; Do[g[x] = 1+x*g[x]*(g[x]^2+g[x]-1) + O[x]^terms // Normal, {terms}]; CoefficientList[g[x], x] (* Jean-François Alcover, Jul 19 2018 *)

a(n) = (1/n) * Sum_{j=0..n} binomial(n, j)*binomial(n+2j, j-1) (n>=1); a(0)=1.
G.f.: G satisfies G = 1 + z*G*(G^2+G-1).
a(n) = hypergeom([1-n,(n+3)/2,(n+4)/2],[2,n+3],-4) for n>=1. - Peter Luschny, Oct 30 2015
a(n) ~ sqrt((s-1) / (Pi*(1 + 3*s))) / (2*n^(3/2) * r^(n + 1/2)), where r = 0.1215851068721183026145063923222031450327682505108... and s = 1.451605962955776643742608112028547116887657025022... are real roots of the system of equations 1 + r*s*(-1 + s + s^2) = s, r*(-1 + 2*s + 3*s^2) = 1. - Vaclav Kotesovec, Nov 27 2017
O.g.f.: A(x) = (1/x) * Revert( x/c(x/(1 - x)) ), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. of the Catalan numbers A000108. - Peter Bala, Mar 08 2020
D-finite with recurrence 8*n*(2*n+1)*a(n) -6*(2*n-1)*(13*n-10)*a(n-1) +24*(4*n-7)*(2*n-5)*a(n-2) +4*(19*n-40)*(n-3)*a(n-3) -35*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jul 26 2022

A108448 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, 7, 61, 575, 5641, 56695, 579125, 5984767, 62390545, 654862247, 6911195501, 73265596607, 779594526361, 8321683861015, 89070157349221, 955598531432447, 10273391096237089, 110647714508386375, 1193641560393864605

Offset: 1

Emeric Deutsch, Jun 10 2005

a(n) = Sum_{k=1..n} k*A108446(n,k). Example: a(3) = 1*32 + 2*13 + 3*1 = 61.

			a(2) = 7 because in the ten paths (ud)(ud), (ud)Udd, u(ud)d, uUddd, Udd(ud), UddUdd, Ud(ud)d, UdUddd, U(ud)dd and UUdddd (see A027307) we have 7 ud's (shown between parentheses).

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

Cf. A027307, A108446, A108426, A108427.

A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3: G:=z*A/(1-2*z*A-3*z*A^2): Gser:=series(G,z=0,25): seq(coeff(Gser,z^n),n=1..23);

RecurrenceTable[{(n-1)*(2*n-1)*a[n]==(18*n^2-26*n+1)*a[n-1] +(46*n^2-225*n+276)*a[n-2]+2*(n-3)*(2*n-5)*a[n-3], a[1]==1, a[2]==7, a[3]==61},a,{n,20}] (* Vaclav Kotesovec, Oct 18 2012 *)

G.f.: z*A/(1-2*z*A-3*z*A^2), where A=1+z*A^2+z*A^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).
Recurrence: (n-1)*(2*n-1)*a(n) = (18*n^2-26*n+1)*a(n-1) + (46*n^2-225*n+276)*a(n-2) + 2*(n-3)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 18 2012
a(n) ~ sqrt(70*sqrt(5)-150)*((11+5*sqrt(5))/2)^n/(20*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 18 2012. Equivalently, a(n) ~ phi^(5*n - 2) / (2 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021
a(n) = Sum_{k=1..n} k*C(n-1,k-1)*C(2*n+k-1,n)/(n+k). - Vladimir Kruchinin, Mar 03 2014
a(n) = P(n-1,n,0,3), where P is the Jacobi Polynomial. - Richard Turk, Jun 27 2018
From Peter Bala, Feb 08 2024: (Start)
a(n) = Sum_{k = 0..n-1} binomial(2*n-1, k)*binomial(n-1, k)*2^k.
(n - 1)*(2*n - 1)*(10*n - 17)*a(n) = (220*n^3 - 814*n^2 + 950*n - 341)*a(n-1) + (n - 2)*(2*n - 3)*(10*n - 7)*a(n-2) with a(1) = 1 and a(2) = 7.. (End)

cp's OEIS Frontend

A108447 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 peaks of the form ud.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula