A002026 -id:A002026 - cp's OEIS frontend

A026269 a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is a nonnegative integer, s(0) = 0 = s(n), s(1) = 1, |s(i) - s(i-1)| <= 1 for i >= 2, |s(2) - s(1)| = 1, |s(3) - s(2)| = 1 if s(2) = 1. Also a(n) = T(n,n) and a(n) = Sum{T(k,k-1)}, k = 1,2,...,n, where T is array in A026268.

1, 2, 4, 10, 25, 64, 166, 436, 1157, 3098, 8360, 22714, 62086, 170614, 471096, 1306374, 3636708, 10159590, 28473132, 80032638, 225562929, 637301652, 1804751718, 5121677512, 14563448593, 41487279622, 118389089432, 338381552294, 968627180975

Offset: 2

Clark Kimberling

nonn

Convolution of [1,2,3,6,13,..] (A005554) with [1,0,1,2,5,12...] (essentially A002026). - R. J. Mathar, Nov 01 2021

Vincenzo Librandi, Table of n, a(n) for n = 2..1000
Gennady Eremin, Arithmetic on Balanced Parentheses: The case of Ordered Motzkin Words, arXiv:1911.01673 [math.CO], 2019. See (4.3) p. 13 (with a different offset).

First differences of A102071.

Drop[CoefficientList[Series[4x^2(1-x^2)/(1-x+Sqrt[1-2x-3x^2])^2, {x,0,30}],x],2] (* Harvey P. Dale, May 05 2011 *)

G.f.: 4z^2(1-z^2)/[1-z+sqrt(1-2z-3z^2)]^2.
D-finite with recurrence (n+2)*a(n) +(-3*n-1)*a(n-1) +(-n+2)*a(n-2) +3*(n-5)*a(n-3)=0. - R. J. Mathar, Jun 10 2013
a(n) ~ 8 * 3^(n-3/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014
a(n) = A002026(n-1) - A002026(n-3). - R. J. Mathar, Nov 01 2021

More terms from Ralf Stephan, Dec 30 2004

A348840 Triangle T(n,h) read by rows: The number of Motzkin Paths of n>=2 steps that start with an Up step and touch the horizontal axis h>=1 times afterwards.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 4, 4, 3, 1, 9, 9, 7, 4, 1, 21, 21, 17, 11, 5, 1, 51, 51, 42, 29, 16, 6, 1, 127, 127, 106, 76, 46, 22, 7, 1, 323, 323, 272, 200, 128, 69, 29, 8, 1, 835, 835, 708, 530, 352, 204, 99, 37, 9, 1, 2188, 2188, 1865, 1415, 965, 587, 311, 137, 46, 10, 1, 5798, 5798, 4963

Offset: 2

R. J. Mathar, Nov 01 2021

To touch means: the path reaches the horizontal line with a down-step, or it is at the horizontal level and takes another horizontal step.

			The triangle starts:
     1
     1    1
     2    2    1
     4    4    3    1
     9    9    7    4    1
    21   21   17   11    5    1
    51   51   42   29   16    6   1
   127  127  106   76   46   22   7   1
   323  323  272  200  128   69  29   8   1
   835  835  708  530  352  204  99  37   9  1
  2188 2188 1865 1415  965  587 311 137  46 10  1
  5798 5798 4963 3805 2647 1667 937 457 184 56 11  1
  ...
T(n,n-1)=1 counts udhhhhh... staying on the horizontal line.
T(4,1)=2 counts uudd, uhhd.
T(4,2)=2 counts udud, uhdh.
T(4,3)=1 counts udhh.
T(5,1)=4 counts uudhd uuhdd uhudd uhhhd.
T(5,2)=4 counts uuddh uduhd uhdud uhhdh.
T(5,3)=3 counts ududh udhud uhdhh.
T(5,4)=1 counts udhhh.

Alois P. Heinz, Rows n = 2..150, flattened

Cf. A002026 (row sums), A001006 (columns h=1,2), A102071 (column h=3).

Cf. A000108, A005322, A344502.

b:= proc(x, y) option remember; expand(`if`(y>x or y<0, 0,
     `if`(x=0, 1, add(b(x-1, y-j), j=-1..1))*`if`(y=0, z, 1)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=1..n-1))(b(n-1, 1)):
seq(T(n), n=2..14);  # Alois P. Heinz, Nov 01 2021

b[x_, y_] := b[x, y] = Expand[If[y > x || y < 0, 0,
     If[x == 0, 1, Sum[b[x - 1, y - j], {j, -1, 1}]]*If[y == 0, z, 1]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 1, n-1}]][b[n-1, 1]];
Table[T[n], {n, 2, 14}] // Flatten (* Jean-François Alcover, Mar 17 2022, after Alois P. Heinz *)

Conjecture: T(n,n-2) = n-2.
Conjecture: T(n,n-3) = A000124(n-3).
Conjecture: T(n,n-4) = -11 + 19*n/3 - 3*n^2/2 + n^3/6.
From Alois P. Heinz, Nov 01 2021: (Start)
Sum_{k=1..n-1} k * T(n,k) = A005322(n).
T(2n,n) = A344502(n-1) for n >= 1. (End)
Conjecture: Riordan array (g(x)^2, x*g(x)), where g(x) = 1/(1 + x)*c(x/(1 + x)) and c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. - Peter Bala, Feb 04 2024

A244884 Expansion of (-2 +x^2 +x -xsqrt(1-2x-3x^2))/(-1 +x -sqrt(1-2x-3*x^2)).

Original entry on oeis.org

1, 1, 1, 2, 5, 12, 30, 76, 196, 512, 1353, 3610, 9713, 26324, 71799, 196938, 542895, 1503312, 4179603, 11662902, 32652735, 91695540, 258215664, 728997192, 2062967382, 5850674704, 16626415975, 47337954326, 135015505407, 385719506620, 1103642686382

Offset: 0

N. J. A. Sloane, Jul 09 2014

nonn

For n > 1, a(n) is the number of Motzkin n-paths that start with an up step. - Gennady Eremin, Sep 18 2021

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from Vincenzo Librandi)
J.-L. Baril and A. Petrossian, Equivalence classes of Dyck paths modulo some statistics, 2014.
Gennady Eremin, Generating function for Naturalized Series: The case of Ordered Motzkin Words, arXiv:2002.08067 [math.CO], 2020.

Apart from initial terms, same as A002026 and A105695.

Cf. A001006.

CoefficientList[Series[(-2 + x^2 + x - x Sqrt[1 - 2 x - 3 x^2])/(-1 + x - Sqrt[1 - 2 x - 3 x^2]), {x, 0, 30}], x] (* Vincenzo Librandi, Jul 10 2014 *)

my(x='x + O('x^50)); Vec((-2 +x^2 +x -x*sqrt(1-2*x-3*x^2))/(-1 +x -sqrt(1-2*x-3*x^2))) \\ G. C. Greubel, Feb 14 2017

a(n) ~ 3^(n+1/2)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jul 10 2014
Conjecture D-finite with recurrence: (n+2)*a(n) +(-3*n-1)*a(n-1) -n*a(n-2) +3*(n-3)*a(n-3)=0. - R. J. Mathar, Jan 24 2020
G.f.: x + (1-x)*M(x), where M(x) is the g.f. of A001006. - Gennady Eremin, Feb 14 2021

A348869 Triangle T(n,c) counting Motzkin Paths of length n with c sections starting with an up-step at level 0.

Original entry on oeis.org

1, 2, 4, 1, 8, 4, 17, 12, 1, 38, 32, 6, 89, 82, 24, 1, 216, 208, 80, 8, 539, 530, 243, 40, 1, 1374, 1364, 702, 160, 10, 3562, 3551, 1975, 564, 60, 1, 9360, 9348, 5484, 1840, 280, 12, 24871, 24858, 15144, 5716, 1125, 84, 1, 66706, 66692, 41768, 17208, 4102, 448, 14

Offset: 2

R. J. Mathar, Nov 02 2021

This is a Sequence Transform of A086615. A086615(n-2) counts the Motzkin Paths of length n which start with an u-step, return to the horizontal level once with a d-step and remain there (with any number of trailing h-steps). These might be called single-return M-Paths. The path of length n=2 is ud. The paths of length 3 are udh, uhd. The Paths of length 4 are uudd, udhh, uhdh and uhhd. A Motzkin Path can be chopped into subpaths of that type by splitting it at each u-step that starts from the horizontal line. [The exception is the path that consists entirely of h-steps.] The triangle of the Sequence Transform T(n,c) counts how many Motzkin Paths of length n which start with an u-step are concatenations of c of these single-return M-paths. T(n,1) are the single-return M-Paths. Row sums and column 1 are an INVERT transform pair.

			The triangle starts
      1
      2
      4     1
      8     4
     17    12     1
     38    32     6
     89    82    24     1
    216   208    80     8
    539   530   243    40    1
   1374  1364   702   160   10
   3562  3551  1975   564   60   1
   9360  9348  5484  1840  280  12
  24871 24858 15144  5716 1125  84  1
  66706 66692 41768 17208 4102 448 14
T(4,2)=1 counts udud.
T(5,1)=8 counts uuddh uudhd uuhdd udhhh uhudd uhdhh uhhdh uhhhd.
T(5,2)=4 counts ududh uduhd udhud uhdud.
T(2n,n) = 1 counts udududu... (ud repeated n times).

Cf. A086615 (column c=1), A002026 (row sums)

A348869 := proc(n,c)
    local g,x,y ;
    g := add( A086615(i)*x^(i+2),i=0..n) ;
    1/(1-y*g) ;
    coeftayl(%,x=0,n) ;
    coeftayl(%,y=0,c) ;
end proc:
seq(seq( A348869(n,c),c=1..n/2),n=2..10) ;

b[n_] := b[n] = If[n <= 3, 2^n, (3*(n+1)*b[n-1] + (n-4)*b[n-2] - 3*(n-1)*b[n-3])/(n+2)];
T[n_, c_] := Module[{g, x, y}, g = Sum[b[i]*x^(i+2), {i, 0, n}]; 1/(1-y*g) // SeriesCoefficient[#, {x, 0, n}]& // SeriesCoefficient[#, {y, 0, c}]&];
Table[T[n, c], {n, 2, 15}, {c, 1, n/2}] // Flatten (* Jean-François Alcover, Aug 12 2023, after Maple code *)

G.f.: 1/(1-y*g086615(x)) where g086615(x) = x^2 +2*x^3 +4*x^4 +8*x^5 +17*x^6 +....

A354511 Number of SAWs crossing a square domain of the hexagonal lattice.

Original entry on oeis.org

2, 14, 264, 21512, 5663596, 6478476233, 23432328776346, 365121393771314359, 18039965927005597824652, 3847346539490622663060402802, 2604549807872636495439504536518768, 7613280873970130888072912524910312775000, 70659728324509466176595292882340210105184200002

Offset: 1

Vaclav Kotesovec, Aug 16 2022

nonn

Anthony J. Guttmann, Table of n, a(n) for n = 1..24
Anthony J. Guttmann and Iwan Jensen, Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices, arXiv:2208.06744 [math-ph], Aug 13 2022, Table D10.

Cf. A001006, A002026, A007764, A116485.

A356610 Number of SAWs crossing a rhomboidal domain of the hexagonal lattice.

Original entry on oeis.org

2, 14, 316, 25092, 7374480, 8029311942, 32223151155864, 476605408516689238, 26016526700583361056456, 5246595079903462547245876694, 3911053741699230141571030313824664, 10780907768757190963361134040036893772360, 109919900687141309301630828947780890728732496678

Offset: 1

Vaclav Kotesovec, following a suggestion from Anthony Guttmann, Aug 16 2022

nonn

Anthony J. Guttmann, Table of n, a(n) for n = 1..26
Anthony J. Guttmann and Iwan Jensen, Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices, arXiv:2208.06744 [math-ph], Aug 13 2022, Table D3.

Cf. A001006, A002026, A007764, A116485.

A356616 Number of SAPs crossing a triangular domain of the hexagonal lattice and including top vertex.

Original entry on oeis.org

1, 1, 4, 36, 666, 24696, 1808820, 259300148, 72369408510, 39205936157880, 41152969216872016, 83592236529606631688, 328284931491454739745904, 2490876950205850778116435156, 36494758452603010620499864088198, 1032033208911845667821292289616451218

Offset: 1

Vaclav Kotesovec, following a suggestion from Anthony Guttmann, Aug 16 2022

nonn

Anthony J. Guttmann, Table of n, a(n) for n = 1..26
Anthony J. Guttmann and Iwan Jensen, Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices, arXiv:2208.06744 [math-ph], Aug 13 2022, Table D9.

Cf. A001006, A002026, A007764, A116485.

A006348 a(n) = (n+2)*a(n-1) + (-1)^n.

Original entry on oeis.org

0, 1, 4, 25, 174, 1393, 12536, 125361, 1378970, 16547641, 215119332, 3011670649, 45175059734, 722800955745, 12287616247664, 221177092457953, 4202364756701106, 84047295134022121, 1764993197814464540, 38829850351918219881, 893086558094119057262

Offset: 1

N. J. A. Sloane

a(n) is a function of the subfactorials... a(n) = A000166(n+2) - 1/3*(n+2)! /Q, i.e., ... 1 = 9 - 24/3, 4 = 44 - 120/3, 25 = 265 - 720/3 ... - Gary Detlefs, Dec 17 2009

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Robert Israel, Table of n, a(n) for n = 1..448
J. A. Sharp & N. J. A. Sloane, Correspondence, 1977

a:= n-> (n+2)!*sum((-1)^k/k!, k=4..n+2): seq(a(n), n=1..23); # Zerinvary Lajos, May 25 2007
a:= n-> floor(((n+2)!+1)/exp(1)) -(n+2)!/3: seq(a(n), n=1..23); # Gary Detlefs, Dec 17 2009

a(n) = (n+1)(a(n-1) + a(n-2)). - Gary Detlefs, Dec 17 2009
E.g.f. with offset 0: ((2 + 3*x + x^3)*exp(-x) - 2)/(1 - x)^4. From int(((9 + 8*x + 6*x^2 + x^4)*exp(-x) - 8)/(1 - x)^5, x) with input 0 for x = 0. - Wolfdieter Lang, May 03 2010
From Robert Israel, Feb 28 2017: (Start)
a(n) = Gamma(n+3, -1)/e - (n+2)!/3.
a(n) ~ (1/e - 1/3) sqrt(2 Pi) n^(n+5/2) exp(-n). (End)

A026940 a(n) = Sum_{k=0..n-1} T(n,k) * T(n,k+1), with T given by A026300.

Original entry on oeis.org

1, 6, 38, 256, 1805, 13162, 98469, 751656, 5831451, 45847770, 364498596, 2925337352, 23668977163, 192859753310, 1581188102590, 13034447714688, 107971181472779, 898274382703314, 7502546644142842, 62884859093960160, 528788663216036559, 4459599092506030110

Offset: 1

Clark Kimberling

nonn

Tewodros Amdeberhan, Moa Apagodu, and Doron Zeilberger, Wilf's "Snake Oil" Method Proves an Identity in The Motzkin Triangle, arXiv:1507.07660 [math.CO], 2015.

Cf. A002026, A026300.

a := n -> n*hypergeom([1/2 - n, 1 - n], [3], 4);
seq(simplify(a(n)), n = 1..22); # Peter Luschny, Sep 05 2022

a[n_] := n Hypergeometric2F1[1/2-n, 1-n, 3, 4]; Array[a, 22] (* Jean-François Alcover, Sep 22 2018 *)

a(n) = sum(k=0, n, binomial(2*n, 2*k+1)*binomial(2*k+1, k)/(k+2)); \\ Michel Marcus, Jul 29 2015

a(n) = Sum_{k=0..n} binomial(2*n, 2*k+1)*binomial(2*k+1, k)/(k+2), see Amdeberhan link. - Michel Marcus, Jul 29 2015
a(n) = n*hypergeom([1/2 - n, 1 - n], [3], 4). - Jean-François Alcover, Sep 22 2018
a(n) = A002026(2*n)/2. - Mark van Hoeij, Sep 05 2022

More terms from Michel Marcus, Jul 29 2015

A105695 Expansion of (1-x)*c(x/(1+x)), where c(x) is the g.f. of the Catalan numbers (A000108).

Original entry on oeis.org

1, 0, 0, 1, 2, 5, 12, 30, 76, 196, 512, 1353, 3610, 9713, 26324, 71799, 196938, 542895, 1503312, 4179603, 11662902, 32652735, 91695540, 258215664, 728997192, 2062967382, 5850674704, 16626415975, 47337954326

Offset: 0

Paul Barry, Apr 17 2005

Apply the Riordan array (1-x,x/(1+x)) to C(n)=A000108(n).

Alternatively, this sequence corresponds to the number of positive walks with n steps {-1,0,1} starting at the origin, ending at altitude 2, and staying strictly above the x-axis. - D. Nguyen, Dec 01 2016.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv:1609.06473 [math.CO], 2016.

Cf. A002026, A005043.

CoefficientList[Series[(1-x^2)*(1-Sqrt[(1-3*x)/(1+x)])/(2*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 01 2014 *)

x='x+O('x^50); Vec((1-x^2)*(1-sqrt((1-3*x)/(1+x)))/(2*x)) \\ G. C. Greubel, Mar 16 2017

G.f.: (1-x^2)*(1-sqrt((1-3*x)/(1+x)))/(2*x).
Let b(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*C(k) = A005043(n); then a(n) = b(n) - b(n-2).
Conjecture: (n+1)*a(n)+(2-3n)*a(n-1) +(1-n)*a(n-2)+3*(n-4)*a(n-3)=0. - R. J. Mathar, Dec 13 2011
a(n) ~ 3^(n-1/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 01 2014
From Peter Bala, Oct 29 2015: (Start)
a(n) = Sum_{k = 1..floor((n-1)/2)} binomial(n-2,2*k-1)*Catalan(k) for n >= 1.
(n+1)*(n-3)*a(n) = (n-2)*(2*n-3)*a(n-1) + 3*(n-2)*(n-3)*a(n-2) with a(2) = 0, a(3) = 1. Mathar's 4-term recurrence above follows easily from this. (End)

cp's OEIS Frontend

A026269 a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is a nonnegative integer, s(0) = 0 = s(n), s(1) = 1, |s(i) - s(i-1)| <= 1 for i >= 2, |s(2) - s(1)| = 1, |s(3) - s(2)| = 1 if s(2) = 1. Also a(n) = T(n,n) and a(n) = Sum{T(k,k-1)}, k = 1,2,...,n, where T is array in A026268.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A348840 Triangle T(n,h) read by rows: The number of Motzkin Paths of n>=2 steps that start with an Up step and touch the horizontal axis h>=1 times afterwards.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A244884 Expansion of (-2 +x^2 +x -x*sqrt(1-2*x-3*x^2))/(-1 +x -sqrt(1-2*x-3*x^2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A348869 Triangle T(n,c) counting Motzkin Paths of length n with c sections starting with an up-step at level 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A354511 Number of SAWs crossing a square domain of the hexagonal lattice.

Views

Author

Keywords

Links

Crossrefs

A356610 Number of SAWs crossing a rhomboidal domain of the hexagonal lattice.

Views

Author

Keywords

Links

Crossrefs

A356616 Number of SAPs crossing a triangular domain of the hexagonal lattice and including top vertex.

Views

Author

Keywords

Links

Crossrefs

A006348 a(n) = (n+2)*a(n-1) + (-1)^n.

Views

Author

Keywords

Comments

References

Links

Programs

Maple

Formula

A026940 a(n) = Sum_{k=0..n-1} T(n,k) * T(n,k+1), with T given by A026300.

Views

Author

Keywords

Links

Crossrefs

A244884 Expansion of (-2 +x^2 +x -xsqrt(1-2x-3x^2))/(-1 +x -sqrt(1-2x-3*x^2)).