A102071 -id:A102071 - cp's OEIS frontend

A005554 Sums of successive Motzkin numbers.

1, 2, 3, 6, 13, 30, 72, 178, 450, 1158, 3023, 7986, 21309, 57346, 155469, 424206, 1164039, 3210246, 8893161, 24735666, 69051303, 193399578, 543310782, 1530523638, 4322488212, 12236130298, 34713220977, 98677591278

Offset: 1

N. J. A. Sloane

nonn

The Donaghey reference shows that a(n) is the number of n-vertex binary trees such that for each non-root vertex that is incident to exactly two edges, these two edges have opposite slope. It also notes that these trees correspond to Dyck n-paths (A000108) containing no DUDUs and no subpaths of the form UUPDD with P a nonempty Dyck path. For example, a(3)=3 counts UUDUDD, UDUUDD, UUDDUD. - David Callan, Sep 25 2006

Hankel transform of the sequence starting with 2 appears to be 3, 4, 5, 6, 7, ... Gary W. Adamson, May 27 2011

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

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
Rosa Orellana, Nancy Wallace, and Mike Zabrocki, Quasipartition and planar quasipartition algebras, Sém. Lotharingien Comb., Proc. 36th Conf. Formal Power Series Alg. Comb. (2024) Vol. 91B, Art. No. 50. See p. 11.
Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 99.

Enumerates the branch-reduced trees encoded by A080981. Cf. A001006.
First differences are in A102071.
Cf. A014138.
A diagonal of A059346.

Rest[CoefficientList[Series[(x+x^2)*(1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2), {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 21 2014 *)

a(n):=(2*sum(binomial(n,j)*binomial(n-j+1,n-2*j+2),j,0,(n+2)/2))/n; /* Vladimir Kruchinin, Oct 04 2015 */

a(n) = sum(k=0, (n+2)/2, 2*(binomial(n,k)*binomial(n-k+1,n-2*k+2)/n));
vector(40, n, if(n==1, 1, a(n-1))) \\ Altug Alkan, Oct 04 2015

Inverse binomial transform of A014138: (1, 3, 8, 22, 64, 196, ...). - Gary W. Adamson, Nov 23 2007
D-finite with recurrence (n + 1)*a(n) = 2*n*a(n - 1) + (3*n - 9)*a(n - 2).
G.f.: (x+x^2)*M(x) where M(x)=(1 - x - (1 - 2*x - 3*x^2)^(1/2))/(2*x^2) is the g.f. for the Motzkin numbers A001006. - David Callan, Sep 25 2006
a(n) = (-1)^n*2*hypergeometric([2-n,5/2],[4],4), for n>1. - Peter Luschny, Aug 15 2012
a(n) ~ 2*3^(n-1/2)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 21 2014
a(n) = (2*Sum_{j=0..(n+2)/2} (binomial(n,j)*binomial(n-j+1,n-2*j+2)))/n. - Vladimir Kruchinin, Oct 04 2015

More terms from James Sellers, Jul 10 2000

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.

Original entry on oeis.org

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

A379907 Triangle read by rows: T(n, k) = Sum_{i=0..n-k} (-1)^(n - k - i) * binomial(n - k, i) * binomial(k + 2i, i) (k + 1) / (k + 1 + i).

Original entry on oeis.org

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

Offset: 0

Werner Schulte, Jan 05 2025

Conjecture: Let A = (g(t), f(t)) and B = (u(t), v(t)) be (triangular) Riordan arrays with A(n, k) = [t^n](g(t)*(f(t))^k) and B(n, k) = [t^n](u(t)*(v(t))^k). Then T = (g(t)*u(f(t)), v(f(t))*t/f(t)) is the Riordan array with T(n, k) = [t^n](g(t)*u(f(t))*(v(f(t))*t/f(t))^k) = Sum_{i=0..n-k} A(n-k, i) * B(k+i, k) for 0 <= k <= n.

			Triangle T(n, k) for 0 <= k <= n starts:
n \k :     0     1     2     3     4    5    6    7    8   9  10  11
====================================================================
   0 :     1
   1 :     0     1
   2 :     1     1     1
   3 :     1     2     2     1
   4 :     3     4     4     3     1
   5 :     6     9     9     7     4    1
   6 :    15    21    21    17    11    5    1
   7 :    36    51    51    42    29   16    6    1
   8 :    91   127   127   106    76   46   22    7    1
   9 :   232   323   323   272   200  128   69   29    8   1
  10 :   603   835   835   708   530  352  204   99   37   9   1
  11 :  1585  2188  2188  1865  1415  965  587  311  137  46  10   1
  etc.

Cf. A005043 (column 0), A001006 (column 1 and 2), A102071 (column 3).

Cf. A000108, A342912 (row sums), A379824 (alternating row sums), A379823 (central terms).

gf := 2/(sqrt((1-3*t)*(t+1)) - 2*(t+1)*t*x + t+1): ser := simplify(series(gf,t,12)):
ct := n -> coeff(ser,t,n): row := n -> local k; seq(coeff(ct(n), x, k), k = 0..n):
seq(row(n), n = 0..11);  # Peter Luschny, Jan 05 2025

T(n,k) = sum(i=0,n-k,(-1)^(n-k-i)*binomial(n-k,i)*binomial(k+2*i,i)*(k+1)/(k+1+i))

T(n,k)=polcoef(polcoef(2/(sqrt((1-3*t)*(1+t))+(1+t)*(1-2*x*t))+x*O(x^k),k,x)+t*O(t^n),n,t);
       m=matrix(15,15,n,k,if(k>n,0,T(n-1,k-1)))

Riordan array (C(t/(1+t)) / (1+t), t * C(t/(1+t))) where C(x) is g.f. of A000108.
Riordan array ((1 + t - sqrt(1 - 2*t - 3*t^2))/(2*t*(1 + t)), (1 + t - sqrt(1-2*t-3*t^2))/2).
G.f.: 2/(sqrt((1 - 3*t)*(t + 1)) - 2*(t + 1)*t*x + t + 1).
Conjecture: T(n, k) = T(n, k-1) + T(n-1, k-1) - T(n-1, k-2) - T(n-2, k-2) for 2 <= k <= n.
T(n, k) = (-1)^(k-n)*hypergeom([k-n, k/2+1, (k+1)/2], [1, k + 2], 4). - Peter Luschny, Jan 06 2025

cp's OEIS Frontend

A005554 Sums of successive Motzkin numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

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

A379907 Triangle read by rows: T(n, k) = Sum_{i=0..n-k} (-1)^(n - k - i) * binomial(n - k, i) * binomial(k + 2*i, i) * (k + 1) / (k + 1 + i).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

PARI

Formula

A379907 Triangle read by rows: T(n, k) = Sum_{i=0..n-k} (-1)^(n - k - i) * binomial(n - k, i) * binomial(k + 2i, i) (k + 1) / (k + 1 + i).