A025179 -id:A025179 - cp's OEIS frontend

A352916 a(n) = A025179(n-2) + A102839(n-4), for n >= 4, with a(0) = a(2) = 0 and a(1) = a(3) = 1.

0, 1, 0, 1, 1, 5, 13, 41, 121, 366, 1100, 3319, 10015, 30253, 91433, 276475, 836291, 2530321, 7657317, 23175867, 70150875, 212349687, 642803631, 1945819299, 5890003539, 17828324220, 53961228258, 163314594513, 494238394601, 1495593167851, 4525366817455

Offset: 0

Kassie Archer, Apr 26 2022

nonn

a(n) + 2*A025565(n) is the number of Dyck paths of semilength n+2 with L(D) = 4 where L(D) is the product of binomial coefficients (u_i(D)+d_i(D) choose u_i(D)), where u_i(D) is the number of up-steps between the i-th and (i+1)-st down step and d_i(D) is the number of down-steps between the i-th and (i+1)-st up step.

Kassie Archer and Christina Graves, Pattern-restricted permutations composed of 3-cycles, arXiv:2104.12664 [math.CO], 2021.
Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.

Cf. A001006, A025179, A025565, A102839.

a:= proc(n) option remember; `if`(n<4, irem(n, 2),
     ((3*(n-4))*(n^4+6*n^3-41*n^2+18*n+76)*a(n-2)+
      (2*n^5+3*n^4-136*n^3+525*n^2-658*n+132)*a(n-1))/
      ((n^4+2*n^3-53*n^2+114*n+12)*(n-1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, May 19 2022

m[n_] := m[n] = If[n == 0, 1, m[n-1] + Sum[m[k]*m[n-2-k], {k, 0, n-2}]];
a[n_] := Switch[n, 0|2, 0, 1|3|4, 1, _, m[n-3] + Binomial[n-3, 2]*m[n-5] + 2*Sum[(i+1)*m[i]*m[n-5-i], {i, 0, n-5}]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 26 2022 *)

m(n) = polcoeff( ( 1 - x - sqrt((1 - x)^2 - 4 * x^2 + x^3 * O(x^n))) / (2 * x^2), n); \\ A001006
a(n) = if (n<=3, n%2, m(n-3) + binomial(n-3,2)*m(n-5) + 2*sum(i=0, n-5, (i+1)*m(i)*m(n-5-i))); \\ Michel Marcus, May 19 2022

a(n) = m(n-3) + binomial(n-3,2)*m(n-5) + 2*Sum_{i=0..n-5} (i+1)*m(i)*m(n-5-i) for n>=3, where m(n) = A001006(n) is the n-th Motzkin number.
a(n) ~ sqrt(n) * 3^(n - 7/2) / (4*sqrt(Pi)). - Vaclav Kotesovec, Jun 03 2022
D-finite with recurrence (n-1)*(n-69)*a(n) +(n^2+221*n-513)*a(n-1) +(-37*n^2+356*n-312)*a(n-2) +(47*n^2-859*n+2820)*a(n-3) +12*(7*n-30)*(n-6)*a(n-4)=0. - R. J. Mathar, Jul 17 2023

A025177 Triangular array, read by rows: first differences in n,n direction of trinomial array A027907.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 2, 4, 4, 4, 2, 1, 1, 3, 7, 10, 12, 10, 7, 3, 1, 1, 4, 11, 20, 29, 32, 29, 20, 11, 4, 1, 1, 5, 16, 35, 60, 81, 90, 81, 60, 35, 16, 5, 1, 1, 6, 22, 56, 111, 176, 231, 252, 231, 176, 111, 56, 22, 6, 1, 1, 7, 29, 84, 189, 343, 518, 659, 714, 659, 518, 343

Offset: 0

Clark Kimberling

The Motzkin transforms of the rows starting (1, 2), (1, 3) and (1, 4), extended by zeros after their last element, are apparently in A026134, A026109 and A026110. - R. J. Mathar, Dec 11 2008

			               1
            1  0  1
         1  1  2  1  1
      1  2  4  4  4  2  1
   1  3  7 10 12 10  7  3  1
1  4 11 20 29 32 29 20 11  4  1

Georg Fischer, Table of n, a(n) for n = 0..2499 [rows 0..49; first 676 terms from _G. C. Greubel_]

Columns include A025178, A025179, A025180, A025181, A025182.

Cf. A024996, A025192 (row sums).

A025177 := proc(n,k)
    option remember;
    if k < 0 or k > 2*n then
        0;
    elif n = 0 then
        1 ;
    elif n = 1 then
        op(k+1,[1,0,1]) ;
    else
        procname(n-1,k-2)+procname(n-1,k-1)+procname(n-1,k) ;
    end if;
end proc:
seq(seq(A025177(n,k),k=0..2*n),n=0..20)  ; # R. J. Mathar, Feb 25 2015

nmax = 10; CoefficientList[CoefficientList[Series[(1 - y*x)/(1 - x*(1 + y + y^2)), {x, 0, nmax}, {y, 0, 2*nmax}], x], y] // Flatten (* G. C. Greubel, May 22 2017; amended by Georg Fischer, Jun 24 2020 *)

{T(n, k) = if( k<0 || k>2*n, 0, if( n==0, 1, if( n==1, [1,0,1][k+1], if( n==2, [1,1,2,1,1][k+1], T(n-1, k-2) + T(n-1, k-1) + T(n-1, k)))))};

T(n,k)=polcoeff(Ser(polcoeff(Ser((1-y*z)/(1-z*(1+y+y^2)),y),k,y),z),n,z)

{T(n, k) = if( k<0 || k>2*n, 0, if( n==0, 1, polcoeff( (1 + x + x^2)^n, k) - polcoeff( (1 + x + x^2)^(n-1), k-1)))};

g=matrix(33,65);
for(n=0,32,for(k=0,2*n,g[n+1,k+1]=0));
g[1,1]=1;
g[2,1]=1;g[2,2]=0;g[2,3]=1;
g[3,1]=1;g[3,2]=1;g[3,3]=2;g[3,4]=1;g[3,5]=1;
for(n=0,2,for(k=0,2*n,print(n," ",k," ",g[n+1,k+1])))
for(n=3,32,g[n+1,1]=1;print(n," 1 1");g[n+1,2]=n-1;print(n," 2 ",n-1);for(k=2,2*n,g[n+1,k+1]=g[n,k-1]+g[n,k]+g[n,k+1];print(n," ",k," ",g[n+1,k+1])))
\\ Michael B. Porter, Feb 02 2010

T(n, k) = T(n-1, k-2) + T(n-1, k-1) + T(n-1, k), starting with [1], [1, 0, 1].

G.f.: (1-y*z)/[1-z*(1+y+y^2)].

Edited by Ralf Stephan, Jan 09 2005

Offset corrected by R. J. Mathar, Feb 25 2015

A024997 a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is an integer, s(0) = 0 = s(n), |s(i) - s(i-1)| = 1 for i = 1,2; |s(i) - s(i-1)| <= 1 for i >= 3. Also a(n) = T(n,n), where T is the array defined in A024996.

Original entry on oeis.org

2, 8, 20, 58, 162, 462, 1318, 3782, 10886, 31436, 91016, 264134, 768094, 2237640, 6529284, 19079574, 55826166, 163538472, 479588844, 1407813438, 4136307798, 12163015662, 35793391662, 105407889930, 310620540202, 915913267652, 2702265079208

Offset: 3

Clark Kimberling

nonn

Second differences of the central trinomial coefficients A002426. - T. D. Noe, Mar 16 2005

G. C. Greubel, Table of n, a(n) for n = 3..1000

Cf. A025179.

Rest[Differences[CoefficientList[Series[1/Sqrt[(1 + x) (1 - 3 x)], {x, 0, 30}], x], 2]] (* Harvey P. Dale, May 11 2013 *)
Table[2 Sum[Binomial[n, 2 k] Binomial[2 k + 1, k + 1], {k, 0, Floor[n/2]}],  {n, 1, 25}] (* G. C. Greubel, Mar 01 2017 *)
Rest[Rest[CoefficientList[Series[((1 - x)^2 - (1 - x) Sqrt[1 - 2 x - 3 x^2])/(x Sqrt[1 - 2 x - 3 x^2]), {x, 0, 15}], x]]] (* G. C. Greubel, Mar 02 2017 *)

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

a(n) = 2*A025179(n-1).
From G. C. Greubel, Mar 01 2017: (Start)
a(n) = 2*Sum_{k=0..floor(n/2)} binomial(n, 2*k)*binomial(2*k+1, k+1), for n>=1.
O.g.f.: ((1-x)^2-(1-x+2*x^2)*sqrt(1-2*x-3*x^2)) / sqrt(1-2*x-3*x^2) [corrected by Charles R Greathouse IV, Mar 05 2017]
E.g.f.: 2*exp(x)*(BesselI(0, 2*x) + BesselI(2, 2*x)). (End)

A026135 Number of (s(0),s(1),...,s(n)) such that every s(i) is a nonnegative integer, s(0) = 1, |s(1) - s(0)| = 1, |s(i) - s(i-1)| <= 1 for i >= 2. Also sum of numbers in row n+1 of the array T defined in A026120.

Original entry on oeis.org

1, 2, 5, 14, 39, 110, 312, 890, 2550, 7334, 21161, 61226, 177575, 516114, 1502867, 4383462, 12804429, 37452870, 109682319, 321563658, 943701141, 2772060618, 8149661730, 23978203662, 70600640796, 208014215066, 613266903927

Offset: 0

Clark Kimberling

nonn

a(n) is the total number of rows of consecutive peaks in all Motzkin (n+2)-paths. For example, with U=upstep, D=downstep, F=flatstep, the path FU(UD)FU(UDUDUD)DD(UD) contains 3 rows of peaks (in parentheses). The 9 Motzkin 4-paths are FFFF, FF(UD), F(UD)F, FUFD, (UD)FF, (UDUD), UFDF, UFFD, U(UD)D, containing a total of 5 rows of peaks and so a(2)=5. - David Callan, Aug 16 2006

G. C. Greubel, Table of n, a(n) for n = 0..1000

First differences are in A025566, second differences in A005773.

Pairwise sums of A025179.

CoefficientList[Series[((x - 1)^2*((1 + x)/(1 - 3 x))^(1/2) + x^2 - 1)/(2*x^2), {x,0,50}], x] (* G. C. Greubel, May 22 2017 *)

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

a(n) = Sum_{k=0..n} binomial(n-1, k-1)*binomial(k+1, floor((k+1)/2)). - Vladeta Jovovic, Sep 18 2003
G.f.: ((x-1)^2*((1+x)/(1-3x))^(1/2) + x^2 - 1)/(2*x^2). - David Callan, Aug 16 2006
G.f. = (1+z)*(1+z^2)/(1-z) where z=x*A001006(x). [From R. J. Mathar, Jul 07 2009]
Conjecture: (n+2)*a(n) +3*(-n-1)*a(n-1) +(-n-2)*a(n-2) +3*(n-3)*a(n-3)=0. - R. J. Mathar, Jun 23 2013

More terms from David Callan, Aug 16 2006

Typo in a(19) corrected by R. J. Mathar, Jul 07 2009

A359364 Triangle read by rows. The Motzkin triangle, the coefficients of the Motzkin polynomials. M(n, k) = binomial(n, k) * CatalanNumber(k/2) if k is even, otherwise 0.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 6, 0, 2, 1, 0, 10, 0, 10, 0, 1, 0, 15, 0, 30, 0, 5, 1, 0, 21, 0, 70, 0, 35, 0, 1, 0, 28, 0, 140, 0, 140, 0, 14, 1, 0, 36, 0, 252, 0, 420, 0, 126, 0, 1, 0, 45, 0, 420, 0, 1050, 0, 630, 0, 42, 1, 0, 55, 0, 660, 0, 2310, 0, 2310, 0, 462, 0

Offset: 0

Peter Luschny, Jan 09 2023

The generalized Motzkin numbers M(n, k) are a refinement of the Motzkin numbers M(n) (A001006) in the sense that they are coefficients of polynomials M(n, x) = Sum_{n..k} M(n, k) * x^k that take the value M(n) at x = 1. The coefficients of x^n are the aerated Catalan numbers A126120.
Variants are the irregular triangle A055151 with zeros deleted, A097610 with reversed rows, A107131 and A080159.
In the literature the name 'Motzkin triangle' is also used for the triangle A026300, which is generated from the powers of the generating function of the Motzkin numbers.

			Triangle M(n, k) starts:
[0] 1;
[1] 1, 0;
[2] 1, 0,  1;
[3] 1, 0,  3, 0;
[4] 1, 0,  6, 0,   2;
[5] 1, 0, 10, 0,  10, 0;
[6] 1, 0, 15, 0,  30, 0,   5;
[7] 1, 0, 21, 0,  70, 0,  35, 0;
[8] 1, 0, 28, 0, 140, 0, 140, 0,  14;
[9] 1, 0, 36, 0, 252, 0, 420, 0, 126, 0;

M. Artioli, G. Dattoli, S. Licciardi, and S. Pagnutti, Motzkin Numbers: an Operational Point of View, arXiv:1703.07262 [math.CO], 2017, (Table 1 on p. 3).

Variants: A055151, A080159, A097610, A107131.
Columns M(n, 2*k): A000012, A000217, A034827, A000910, A088625, A088626, A213380.
Cf. A001006 (Motzkin numbers), A026300 (Motzkin gf. triangle), A126120 (aerated Catalan), A000108 (Catalan).
Cf. A138364, A107587, A002457, A002522, A025179, A025235, A056107, A014531, A023426, A091147, A189912, A343386, A343773, A359647, A359649.

CatalanNumber := n -> binomial(2*n, n)/(n + 1):
M := (n, k) -> ifelse(irem(k, 2) = 1, 0, CatalanNumber(k/2)*binomial(n, k)):
for n from 0 to 9 do seq(M(n, k), k = 0..n) od;
# Alternative, as coefficients of polynomials:
p := n -> hypergeom([(1 - n)/2, -n/2], [2], (2*x)^2):
seq(print(seq(coeff(simplify(p(n)), x, k), k = 0..n)), n = 0..9);
# Using the exponential generating function:
egf := exp(x)*BesselI(1, 2*x*t)/(x*t): ser:= series(egf, x, 11):
seq(print(seq(coeff(simplify(n!*coeff(ser, x, n)), t, k), k = 0..n)), n = 0..9);

from functools import cache
@cache
def M(n: int, k: int) -> int:
    if k %  2: return 0
    if n <  3: return 1
    if n == k: return (2 * (n - 1) * M(n - 2, n - 2)) // (n // 2 + 1)
    return (M(n - 1, k) * n) // (n - k)
for n in range(10): print([M(n, k) for k in range(n + 1)])

Let p(n, x) = hypergeom([(1 - n)/2, -n/2], [2], (2*x)^2).
p(n, 1) = A001006(n); p(n, sqrt(2)) = A025235(n); p(n, 2) = A091147(n).
p(2, n) = A002522(n); p(3, n) = A056107(n).
p(n, n) = A359649(n); 2^n*p(n, 1/2) = A000108(n+1).
M(n, k) = [x^k] p(n, x).
M(n, k) = [t^k] (n! * [x^n] exp(x) * BesselI(1, 2*t*x) / (t*x)).
M(n, k) = [t^k][x^n] ((1 - x - sqrt((x-1)^2 - (2*t*x)^2)) / (2*(t*x)^2)).
M(n, n) = A126120(n).
M(n, n-1) = A138364(n), the number of Motzkin n-paths with exactly one flat step.
M(2*n, 2*n) = A000108(n), the number of peakless Motzkin paths having a total of n up and level steps.
M(4*n, 2*n) = A359647(n), the central terms without zeros.
M(2*n+2, 2*n) = A002457(n) = (-4)^n * binomial(-3/2, n).
Sum_{k=0..n} M(n - k, k) = A023426(n).
Sum_{k=0..n} k * M(n, k) = 2*A014531(n-1) = 2*GegenbauerC(n - 2, -n, -1/2).
Sum_{k=0..n} i^k*M(n, k) = A343773(n), (i the imaginary unit), is the excess of the number of even Motzkin n-paths (A107587) over the odd ones (A343386).
Sum_{k=0..n} Sum_{j=0..k} M(n, j) = A189912(n).
Sum_{k=0..n} Sum_{j=0..k} M(n, n-j) = modified A025179(n).
For a recursion see the Python program.

A026079 a(n) = Sum_{k = 1..n} T(k,k-1), where T is the array defined in A024996.

Original entry on oeis.org

1, 3, 6, 12, 31, 83, 233, 661, 1893, 5445, 15720, 45510, 132069, 384049, 1118822, 3264644, 9539789, 27913085, 81769238, 239794424, 703906721, 2068153901, 6081507833, 17896695833, 52703944967, 155310270103, 457956633828, 1351132539606, 3988457429607

Offset: 1

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A025179.

Join[{1, 3}, Table[Sum[ Binomial[n, 2*k]*Binomial[2*k + 1, k + 1], {k, 0, Floor[n/2]}] + 2, {n,2,50}]] (* G. C. Greubel, May 22 2017 *)

concat([1,3], for(n=2,50, print1(2 + sum(k=0,floor(n/2), binomial(n, 2*k)*binomial(2*k+1, k+1)), ", "))) \\ G. C. Greubel, May 22 2017

a(n) = A025179(n) + 2, n>2.

cp's OEIS Frontend

A352916 a(n) = A025179(n-2) + A102839(n-4), for n >= 4, with a(0) = a(2) = 0 and a(1) = a(3) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A025177 Triangular array, read by rows: first differences in n,n direction of trinomial array A027907.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

Extensions

A024997 a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is an integer, s(0) = 0 = s(n), |s(i) - s(i-1)| = 1 for i = 1,2; |s(i) - s(i-1)| <= 1 for i >= 3. Also a(n) = T(n,n), where T is the array defined in A024996.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A026135 Number of (s(0),s(1),...,s(n)) such that every s(i) is a nonnegative integer, s(0) = 1, |s(1) - s(0)| = 1, |s(i) - s(i-1)| <= 1 for i >= 2. Also sum of numbers in row n+1 of the array T defined in A026120.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A359364 Triangle read by rows. The Motzkin triangle, the coefficients of the Motzkin polynomials. M(n, k) = binomial(n, k) * CatalanNumber(k/2) if k is even, otherwise 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

A026079 a(n) = Sum_{k = 1..n} T(k,k-1), where T is the array defined in A024996.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula