A005773 -id:A005773 - cp's OEIS frontend

A364645 G.f. satisfies A(x) = 1/(1 - 3x) - xA(x)^3.

1, 2, 3, 6, 19, 51, 114, 312, 981, 2616, 6564, 19647, 59922, 159056, 430302, 1329996, 3926217, 10498968, 30052851, 93244764, 267690168, 729649143, 2173840338, 6663260223, 18768583674, 52570016676, 160362713250, 481809941520, 1346473504182, 3886164785178

Offset: 0

Seiichi Manyama, Jul 31 2023

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A364641, A364646, A364647.

Cf. A005773, A349254, A349256, A349534.

a(n) = sum(k=0, n, (-1)^k*3^(n-k)*binomial(n+k, 2*k)*binomial(3*k, k)/(2*k+1));

a(n) = Sum_{k=0..n} (-1)^k * 3^(n-k) * binomial(n+k,2*k) * binomial(3*k,k) / (2*k+1).

A054393 Number of permutations with certain forbidden subsequences.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 428, 1417, 4757, 16119, 54963, 188219, 646460, 2224944, 7668915, 26461005, 91371594, 315689675, 1091166442, 3772747245, 13047503222, 45131078409, 156129312025, 540181837728, 1869097588540, 6467740095295

Offset: 0

N. J. A. Sloane, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000

nonn

E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
Nickolas Hein, Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108).

Cf. A005773, A054391, A054392, A054394.

a[0] = 1; a[n_] := Module[{M}, M = Table[If[j < i || i == j && i <= 5 || j == i+1, 1, 0], {i, 1, n}, {j, 1, n}]; MatrixPower[M, n][[1, 1]]];
Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Aug 16 2018, after A054391 *)

Conjecture: (-n+3)*a(n) + (10*n-33)*a(n-1) + 5*(-7*n+24)*a(n-2) + 2*(22*n-63)*a(n-3) + 2*(5*n-78)*a(n-4) + (-55*n+357)*a(n-5) + (22*n-135)*a(n-6) + 3*(-n+6)*a(n-7) = 0. - R. J. Mathar, Aug 09 2015

A059714 Number of stacked directed animals on the triangular lattice.

Original entry on oeis.org

1, 3, 11, 44, 184, 789, 3435, 15100, 66806, 296870, 1323318, 5911972, 26455294, 118528793, 531540891, 2385375732, 10710619014, 48112492938, 216195753066, 971744791032, 4368674392104, 19643610378738, 88339070102046, 397313118498744, 1787115246076764

Offset: 1

Mireille Bousquet-Mélou, Feb 08 2001

nonn

Closely related to directed animals. A square lattice version exists.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers
M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers, Discrete Math. 258 (2002), no. 1-3, 235-274.
M. Bousquet-Mélou and S. Butler, Forest-like permutations, arXiv:math/0603617 [math.CO], 2006.
Kyu-Hwan Lee, Se-jin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.

Cf. A005773.

gf := ((1-3*x)*(1-4*x)-(1-5*x)*sqrt(1-4*x))/(2*x*(2-9*x)): s := series(gf, x, 50): for i from 1 to 100 do printf(`%d,`,coeff(s,x,i)) od:

Rest[Table[SeriesCoefficient[((1-3*x)*(1-4*x)-(1-5*x)*Sqrt[1-4*x])/(2*x*(2-9*x)),{x,0,n}],{n,0,20}]] (* Vaclav Kotesovec, Oct 28 2012 *)
Flatten[{1,Table[3^(2*n-2)/2^n* (2 - Sum[(k+8)*Binomial[2*k,k]*2^k/((k+1)*(k+2)*3^(2*k)),{k,1,n-1}]),{n,2,20}]}] (* Vaclav Kotesovec, Oct 28 2012 *)

a(n):=sum((k+1)*2^(k-1)*binomial(2*n,n-k-1),k,1,n-1)/n+binomial(2*n,n-1)/n; /* Vladimir Kruchinin, Jun 08 2016 */

x = 'x + O('x^40); Vec(((1-3*x)*(1-4*x)-(1-5*x)*sqrt(1-4*x))/(2*x*(2-9*x))) \\ Michel Marcus, Jan 28 2016

G.f.: ((1-3*x)*(1-4*x)-(1-5*x)*sqrt(1-4*x))/(2*x*(2-9*x)).
2*(n+1)*a(n) +(5-27*n)*a(n-1) +(121*n-163)*a(n-2) +90*(5-2*n)*a(n-3) =0. - R. J. Mathar, Aug 14 2012 [See following Israel's contribution.]
a(n) ~ 3^(2*n-1)/2^(n+2). - Vaclav Kotesovec, Oct 11 2012
a(n) = 3^(2*n-2)/2^n*(2-Sum_{k=1..n-1} (k+8)*C(2*k,k)*2^k/((k+1)*(k+2)*3^(2*k)) ), for n>1. - Vaclav Kotesovec, Oct 28 2012
a(n) = Sum_{k=1..n-1} (k+1)*2^(k-1)*binomial(2*n,n-k-1)/n + binomial(2*n,n-1)/n. - Vladimir Kruchinin, Jun 08 2016
G.f. satisfies 60*x^3-31*x^2+4*x+(90*x^3-79*x^2+22*x-2)*g(x)+(180*x^4-121*x^3+27*x^2-2*x)*g'(x) = 0, from which Mathar's recurrence follows. - Robert Israel, Jun 08 2016
G.f. F satisfies 0 = F^2*(9*x^2 - 2*x) + F*(12*x^2 - 7*x + 1) + 4*x^2 - x. - F. Chapoton, Oct 16 2021

More terms from James Sellers, Feb 09 2001

A098494 Triangle read by rows: coefficients of polynomials E(n,x) related to partitions with parts occurring at most thrice.

Original entry on oeis.org

1, 1, -1, 1, -5, 4, 1, -12, 35, -30, 1, -22, 143, -362, 312, 1, -35, 405, -2065, 4814, -4200, 1, -51, 925, -7965, 35434, -78744, 69120, 1, -70, 1834, -24010, 173929, -709240, 1525236, -1345680, 1, -92, 3290, -61040, 655529, -4235588, 16255420, -34148400, 30240000

Offset: 0

Ralf Stephan, Sep 12 2004

The polynomials generate (-1)^k*n! times the diagonals of A098493.

			E(0,x) = 1
E(1,x) = x - 1
E(2,x) = x^2 - 5*x + 4
E(3,x) = x^3 - 12*x^2 + 35*x - 30
E(4,x) = x^4 - 22*x^3 + 143*x^2 - 362*x + 312
E(5,x) = x^5 - 35*x^4 + 405*x^3 - 2065*x^2 + 4814*x - 4200

Seiichi Manyama, Rows n = 0..139, flattened
Alex Fink, Richard K. Guy, and Mark Krusemeyer, Partitions with parts occurring at most thrice, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76-114.

Columns include -A000326.
Constant terms E(n, 0) = -E(n-1, -1) = n!/2*A085455 = (-1)^n*n!*A005773.
Row sums are E(n, 1) = (-1)^n*n!*A005774(n-2). [corrected by Seiichi Manyama, Feb 04 2023]

E(n+1,x+1) - E(n+1,x) = (n+1) * ( E(n,x) - n * E(n-1,x-1) ).

A122899 Triangle with row sums counting directed animals.

Original entry on oeis.org

1, 1, 1, 0, 4, 1, 0, 3, 9, 1, 0, 0, 18, 16, 1, 0, 0, 10, 60, 25, 1, 0, 0, 0, 80, 150, 36, 1, 0, 0, 0, 35, 350, 315, 49, 1, 0, 0, 0, 0, 350, 1120, 588, 64, 1, 0, 0, 0, 0, 126, 1890, 2940, 1008

Offset: 0

Paul Barry, Sep 18 2006

Row sums are A005773(n+1). Product of A007318 and A122899 is A103371.

			Triangle begins
1,
1, 1,
0, 4, 1,
0, 3, 9, 1,
0, 0, 18, 16, 1,
0, 0, 10, 60, 25, 1,
0, 0, 0, 80, 150, 36, 1,
0, 0, 0, 35, 350, 315, 49, 1,
0, 0, 0, 0, 350, 1120, 588, 64, 1,
0, 0, 0, 0, 126, 1890, 2940, 1008, 81, 1,
0, 0, 0, 0, 0, 1512, 7350, 6720, 1620, 100, 1

Cf. A123160.

Number triangle T(n,k)=sum{j=0..n, (-1)^(n-j)C(n,j)C(j+1,k+1)C(j,k)}

T(n,k) = C(n,k)*C(k+1,n-k). The columns of this triangle (ignoring leading zeros) give the rows of A123160. - Peter Bala, Jan 24 2008

A123149 Triangle T(n,k), 0<=k<=n, read by rows given by [1, 0, -1, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 0, -1, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 5, 5, 3, 1, 0, 1, 3, 6, 7, 6, 3, 1, 0, 1, 4, 9, 13, 13, 9, 4, 1, 0, 1, 4, 10, 16, 19, 16, 10, 4, 1, 0, 1, 5, 14, 26, 35, 35, 26, 14, 5, 1, 0, 1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1, 0, 1, 6, 20, 45, 75, 96, 96, 75, 45, 20, 6, 1, 0

Offset: 0

Philippe Deléham, Nov 05 2006

A169623 is a very similar triangle except it does not have the outer diagonal of 0's. - N. J. A. Sloane, Nov 23 2017

			Triangle begins:
  1;
  1,  0;
  1,  1,  0;
  1,  1,  1,  0;
  1,  2,  2,  1,  0;
  1,  2,  3,  2,  1,  0;
  1,  3,  5,  5,  3,  1,  0;
  1,  3,  6,  7,  6,  3,  1,  0;
  1,  4,  9, 13, 13,  9,  4,  1,  0;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A002426, A005773, A013979, A027907, A038754, A084938, A135528, A169623, A182522 (row sums).

function T(n,k) // T = A123149
  if k lt 0 or k gt n then return 0;
  elif k eq 0 or k eq n-1 then return 1;
  elif k eq n then return 0;
  else return T(n-2,k) +T(n-2,k-1) +T(n-2,k-2);
  end if;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jul 17 2023

T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[k==0 || k==n-1, 1, If[k==n, 0, T[n-2,k] +T[n-2,k-1] +T[n-2,k-2] ]]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Jul 17 2023 *)

def T(n,k): # T = A123149
    if (k<0 or k>n): return 0
    elif (k==0 or k==n-1): return 1
    elif (k==n): return 0
    else: return T(n-2,k) +T(n-2,k-1) +T(n-2,k-2)
flatten([[T(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Jul 17 2023

T(n,k) = T(n-1,k-1) + T(n-1,k) if n even, T(n,k) = T(n-1,k-1) + T(n-2,k) if n odd, T(0,0) = 1, T(1,0) = 1, T(1,1) = 0, T(n,k) = 0 if k < 0 or if k > n.
T(n,k) = T(n,n-k-1).
Sum_{k=0..n} T(n,k) = A038754(n-1), for n>=1.
T(2*n,n) = A005773(n).
T(2*n+1,n) = A002426(n).
From Philippe Deléham, May 04 2012: (Start)
G.f.: (1+x-y^2*x^2)/(1-x^2-y*x^2-y^2*x^2).
T(n,k) = T(n-2,k) + T(n-2,k-1) + T(n-2,k-2), T(0,0) = T(1,0) = T(2,0) = T(2,1) = 1, T(1,1) = T(2,2) = 0 and T(n,k) = 0 if k < 0 or if k > n.
Sum_{k=0..n} T(n,k) = A182522(n). (End)
From G. C. Greubel, Jul 17 2023: (Start)
Sum_{k=0..n} (-1)^k*T(n,k) = A135528(n).
Sum_{k=0..floor(n/2)} T(n-k,k) = [n==0] + A013979(n+1). (End)

A245455 Number of minimax elements in the affine Weyl group of the Lie algebra so(2n).

Original entry on oeis.org

1, 3, 4, 9, 23, 61, 166, 459, 1284, 3623, 10292, 29395, 84327, 242807, 701314, 2031085, 5895951, 17150013, 49975428, 145862571, 426337773, 1247741271, 3655973226, 10723668081, 31485145902, 92524150845, 272120203908, 800931753629, 2359038637409, 6952768502473

Offset: 1

Peter Bala, Jul 22 2014

See A005773 for the number of minimax elements in the affine Weyl group of the Lie algebra so(2n+1).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
D. I. Panyushev, Ideals of Heisenberg type and minimax elements of affine Weyl groups, arXiv:math/0311347 [math.RT], Lie Groups and Invariant Theory, Amer. Math. Soc. Translations, Series 2, Volume 213, (2005), ed. E. Vinberg

Cf. A005773.

A245455 := proc(n)
    coeftayl(x/2*(1+2*x)*(1+sqrt(1-2*x-3*x^2)/(1-3*x)), x=0, n);
end proc:
seq(A245455(n), n=1..30); # Wesley Ivan Hurt, Jul 26 2014

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

a(n) = A005773(n-1) + 2*A005773(n-2).
O.g.f.: x/2*(1+2*x)*( 1 + sqrt(1-2*x-3*x^2)/(1-3*x) ).
a(n) ~ 5*3^(n-5/2) / sqrt(Pi*n). - Vaclav Kotesovec, Jul 25 2014
(-n+1)*a(n) +4*(1)*a(n-1) +7*(n-3)*a(n-2) +6*(n-5)*a(n-3)=0. - R. J. Mathar, Sep 06 2016
(5*n-4)*(n-1)*a(n) +2*(-5*n^2+9*n-10)*a(n-1) -3*(5*n+1)*(n-4)*a(n-2)=0. - R. J. Mathar, Sep 06 2016

A283595 Triangle read by rows: T(n,k) is the number of Motzkin prefixes (i.e., left factors of Motzkin paths) of length n and height k.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 4, 1, 1, 15, 13, 5, 1, 1, 31, 38, 19, 6, 1, 1, 63, 105, 64, 26, 7, 1, 1, 127, 280, 202, 97, 34, 8, 1, 1, 255, 729, 612, 334, 139, 43, 9, 1, 1, 511, 1866, 1803, 1094, 516, 191, 53, 10, 1, 1, 1023, 4717, 5205, 3465, 1802, 760, 254, 64, 11, 1

Offset: 0

Steven Finch, Mar 13 2017

Row n has n+1 entries.

			Triangle starts:
  1;
  1,  1;
  1,  3,  1;
  1,  7,  4,  1;
  1, 15, 13,  5,  1;
  1, 31, 38, 19,  6,  1;
  ...
T(3,2) = 4 because we have UHU, HUU, UUD and UUH, where U=(1,1), D=(1,-1), H=(1,0).
T(3,1) = 7 because we have UDH, HUD, UHD, UHH, HUH, HHU and UDU.

Alois P. Heinz, Rows n = 0..140, flattened
Steven R. Finch, How far might we walk at random?, arXiv:1802.04615 [math.HO], 2018.

Row sums give A005773(n+1).
T(2n,n) gives A283667.
Cf. A000225, A097862, A282869.

b:= proc(x, y, m) option remember; `if`(x=0, z^m, b(x-1, y, m)+
      `if`(y>0, b(x-1, y-1, m), 0)+b(x-1, y+1, max(m, y+1)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..n))(b(n, 0$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Mar 13 2017

b[x_, y_, m_] := b[x, y, m] = If[x==0, z^m, b[x-1, y, m] + If[y>0, b[x-1, y - 1, m], 0] + b[x-1, y+1, Max[m, y+1]]]; T[n_] := Function[p, Table[ Coefficient[p, z, i], {i, 0, n}]][b[n, 0, 0]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 18 2017, after Alois P. Heinz *)

More terms from Alois P. Heinz, Mar 13 2017

A378941 Number of Motzkin paths of length n up to reversal.

Original entry on oeis.org

1, 1, 2, 3, 7, 13, 32, 70, 179, 435, 1142, 2947, 7889, 21051, 57192, 155661, 427795, 1179451, 3271214, 9102665, 25434661, 71282431, 200406472, 564905068, 1596435581, 4521772933, 12835116530, 36504093693, 104012240063, 296871993373, 848694481664, 2429882584254, 6966789756243

Offset: 0

Andrew Howroyd, Dec 17 2024

nonn

A Motzkin path of length n is a path from (0,0) to (n,0) using only steps U = (1,1), H = (1,0) and D = (1,-1). This sequence considers a path and its reversal to be the same. The number of symmetric paths of length 2n (and also 2n+1) is given by A005773(n+1).

a(n) + 1 is an upper bound on the order of the linear recurrence of column n-1 of A287151. At least for columns up to 7, this bound gives the actual order of the recurrence. For example, a(5) = 13 and the order of the recurrence of column 4 (=A059524) is 14.

			The Motzkin paths for a(1)..a(5) are:
a(1) = 1: H;
a(2) = 2: HH, UD;
a(3) = 3: HHH, UHD, HUD=UDH;
a(4) = 7: HHHH, HUDH, UHHD, UUDD, UDUD, HHUD=UDHH, HUHD=UHDH.
a(5) = 13: HHHHH, HUHDH, UHHHD, UUHDD, UDHUD, HHHUD=UDHHH, HHUHD=UHDHH, HHUDH=HUDHH, HUHHD=UHHDH, HUUDD=UUDDH, HUDUD=UDUDH, UHUDD=UUHDD, UHDUD=UPUHD.

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A001006, A005773, A007123 (similar for Dyck paths), A175954, A185100, A287151, A292357.

Vec(-3/(4*x)-(1+sqrt(1-2*x-3*x^2+O(x^40)))/(4*x^2)+(1+x)/(-1+3*x^2+sqrt(1-2*x^2-3*x^4+O(x^40)))) \\ Thomas Scheuerle, Dec 18 2024

a(n) = (A001006(n) + A005773(floor(1 + n/2))) / 2.

A054394 Number of permutations with certain forbidden subsequences.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1429, 4847, 16660, 57820, 202086, 709928, 2503266, 8850681, 31355020, 111242127, 395091069, 1404332528, 4994581900, 17771328588, 63253477326, 225194224134, 801884971816, 2855809269782, 10171707099565

Offset: 0

N. J. A. Sloane, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000

nonn

E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
Nickolas Hein, Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). Cf. A005773, A054391-A054393.

a[0] = 1; a[n_] := Module[{M}, M = Table[If[j < i || i == j && i <= 6 || j == i+1, 1, 0], {i, 1, n}, {j, 1, n}]; MatrixPower[M, n][[1, 1]]];
Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Aug 16 2018, after A054391 *)

Conjecture: g.f.(x)=1+z*(1-2z+z^2-z^3)/(1-3z+3z^2-3z^3+2z^4-z^5) where z=x*A001006(x) and A001006(x) is the g.f. of A001006. [R. J. Mathar, Jul 07 2009]

cp's OEIS Frontend

A364645 G.f. satisfies A(x) = 1/(1 - 3*x) - x*A(x)^3.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A054393 Number of permutations with certain forbidden subsequences.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A059714 Number of stacked directed animals on the triangular lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A098494 Triangle read by rows: coefficients of polynomials E(n,x) related to partitions with parts occurring at most thrice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A122899 Triangle with row sums counting directed animals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A123149 Triangle T(n,k), 0<=k<=n, read by rows given by [1, 0, -1, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 0, -1, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A245455 Number of minimax elements in the affine Weyl group of the Lie algebra so(2n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A283595 Triangle read by rows: T(n,k) is the number of Motzkin prefixes (i.e., left factors of Motzkin paths) of length n and height k.

Views

Author

Keywords

Comments

Examples

A364645 G.f. satisfies A(x) = 1/(1 - 3x) - xA(x)^3.