A108441 -id:A108441 - cp's OEIS frontend

A108442 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 only u steps among the steps leading to the first d step.

1, 1, 3, 15, 97, 721, 5827, 49759, 441729, 4035937, 37702723, 358474735, 3457592161, 33748593841, 332730216579, 3308635650495, 33145196426753, 334193815799233, 3388807714823043, 34537227997917391, 353578650475659617, 3634495706671023505, 37496621681376849219, 388135791657414454815

Offset: 0

Emeric Deutsch, Jun 08 2005

nonn

			a(2)=3 because we have udud, udUdd and uudd.

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

Column 0 of A108441.

Cf. A027307, A108441.

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

Flatten[{1,Table[Sum[k*Sum[Binomial[2*n-k, i]*Binomial[3*n-2*k-i-1, 2*n-k-1], {i, 0, n-k}]/(2*n-k), {k, 1, n}],{n,1,20}]}] (* Vaclav Kotesovec, Mar 17 2014, after Vladimir Kruchinin *)

a(n):=if n=0 then 1 else sum((k*sum(binomial(2*n-k,i)*binomial(3*n-2*k-i-1,2*n-k-1),i,0,n-k))/(2*n-k),k,1,n); /* Vladimir Kruchinin, Oct 23 2011 */

G.f.: 1/(1-z*A), where A = 1 + z*A^2 + z*A^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).
a(n) = Sum_{k=1..n} (k*(Sum_{i=0..n-k} binomial(2*n-k, i)*binomial(3*n-2*k-i-1, 2*n-k-1))/(2*n-k)), n > 0, a(0)=1. - Vladimir Kruchinin, Oct 23 2011
G.f. y(x) satisfies: (3+x)*y*(1-y) + (1+x^2)*y^3 = 1. - Vaclav Kotesovec, Mar 17 2014
a(n) ~ (11+5*sqrt(5))^n / (5^(5/4) * sqrt(Pi) * n^(3/2) * 2^(n+1)). - Vaclav Kotesovec, Mar 17 2014
D-finite with recurrence (2*n-1)*(n-1)*a(n) +6*(n^2-10*n+13)*a(n-1) +(-310*n^2+1869*n-2759)*a(n-2) +48*(-n+3)*a(n-3) +(-310*n^2+1851*n-2705)*a(n-4) +6*(-n^2+2*n+11)*a(n-5) +(n-5)*(2*n-11)*a(n-6)=0. - R. J. Mathar, Jul 26 2022

A108440 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 having k u=(2,1) steps among the steps leading to the first d step.

Original entry on oeis.org

1, 1, 1, 5, 4, 1, 33, 25, 7, 1, 249, 184, 54, 10, 1, 2033, 1481, 446, 92, 13, 1, 17485, 12620, 3863, 846, 139, 16, 1, 156033, 111889, 34637, 7881, 1411, 195, 19, 1, 1431281, 1021424, 318812, 74492, 14102, 2168, 260, 22, 1, 13412193, 9536113, 2995228

Offset: 0

Emeric Deutsch, Jun 08 2005

			T(2,1)=4 because we have udud, udUdd, uUddd and Uuddd.
Triangle begins:
.1;
.1,1;
.5,4,1;
.33,25,7,1;
.249,184,54,10,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.

Row sums yield A027307. Column 0 yields A034015.

Cf. A027307, A034015, A108441.

A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3: G:=1/(1-t*z*A-z*A^2): 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
# 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, false)+b(x-1, y+2, t)+
       b(x-2, y+1, t)*`if`(t, z, 1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..n))(b(3*n, 0, true)):
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, False] + b[x - 1, y + 2, t] + b[x - 2, y + 1, t]*If[t, z, 1]]]]; T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, n}]][ b[3*n, 0, True]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 29 2016, after Alois P. Heinz *)

G.f.: G(t, z)=1/(1-tzA-zA^2)-1, 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).

cp's OEIS Frontend

A108442 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 only u steps among the steps leading to the first d step.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula