A005773 -id:A005773 - cp's OEIS frontend

A113408 Riordan array (1/(1-x^2-x^4c(x^4)),xc(x^2)), c(x) the g.f. of A000108.

1, 0, 1, 1, 0, 1, 0, 2, 0, 1, 2, 0, 3, 0, 1, 0, 6, 0, 4, 0, 1, 3, 0, 12, 0, 5, 0, 1, 0, 12, 0, 20, 0, 6, 0, 1, 6, 0, 30, 0, 30, 0, 7, 0, 1, 0, 30, 0, 60, 0, 42, 0, 8, 0, 1, 10, 0, 90, 0, 105, 0, 56, 0, 9, 0, 1, 0, 60, 0, 210, 0, 168, 0, 72, 0, 10, 0, 1, 20, 0, 210, 0, 420, 0, 252, 0, 90, 0, 11, 0, 1

Offset: 0

Paul Barry, Oct 28 2005

Row sums are A113409. Diagonal sums are A005773(n+1) with interpolated zeros.

			Triangle begins
1;
0,1;
1,0,1;
0,2,0,1;
2,0,3,0,1;
0,6,0,4,0,1;
3,0,12,0,5,0,1;

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Table[Binomial[(n + k)/2, k]*Binomial[Floor[(n - k)/2], Floor[(n - k)/4]]*(1 + (-1)^(n - k))/2, {n, 0, 49}, {k, 0, n}] // Flatten (* G. C. Greubel, Mar 09 2017 *)

for(n=0,25, for(k=0,n, print1( binomial((n+k)/2,k) *binomial(floor((n-k)/2),floor((n-k)/4))*(1+(-1)^(n-k))/2, ", "))) \\ G. C. Greubel, Mar 09 2017

T(n, k) = C((n+k)/2,k)*C(floor((n-k)/2),floor((n-k)/4))(1+(-1)^(n-k))/2.

A114690 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n and having k weak ascents (1 <= k <= ceiling(n/2)).

Original entry on oeis.org

1, 2, 3, 1, 5, 4, 8, 12, 1, 13, 31, 7, 21, 73, 32, 1, 34, 162, 116, 11, 55, 344, 365, 70, 1, 89, 707, 1041, 335, 16, 144, 1416, 2762, 1340, 135, 1, 233, 2778, 6932, 4726, 820, 22, 377, 5358, 16646, 15176, 4039, 238, 1, 610, 10188, 38560, 45305, 17157, 1785, 29, 987

Offset: 1

Emeric Deutsch, Dec 24 2005

A Motzkin path of length n is a lattice path from (0,0) to (n,0) consisting of U=(1,1), D=(1,-1) and H=(1,0) steps and never going below the x-axis. A weak ascent in a Motzkin path is a maximal sequence of consecutive U and H steps.
Row n has ceiling(n/2) terms.
Row sums are the Motzkin numbers (A001006).
Column 1 yields the Fibonacci numbers (A000045).
Sum_{k=1..ceiling(n/2)} k*T(n,k) = A005773(n).

			T(4,2)=4 because we have (HU)D(H),(U)D(HH),(U)D(U)D and (UH)D(H) (the weak ascents are shown between parentheses).
Triangle starts:
   1;
   2;
   3,  1;
   5,  4;
   8, 12,  1;
  13, 31,  7;
  ...

Alois P. Heinz, Rows n = 1..200, flattened
Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Consecutive patterns in restricted permutations and involutions, arXiv:1902.02213 [math.CO], 2019.

Cf. A001006, A005773, A000045, A114655.

G:=(1-t*z^2-z-z^2-sqrt(1-2*t*z^2-2*z-z^2+t^2*z^4-2*t*z^3-2*z^4*t+2*z^3+z^4))/2/z^2: Gser:=simplify(series(G,z=0,18)): for n from 1 to 15 do P[n]:=coeff(Gser,z^n) od: for n from 1 to 15 do seq(coeff(P[n],t^j),j=1..ceil(n/2)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, t,
      b(x-1, y+1, z)+expand(b(x-1, y-1, 1)*t)+b(x-1, y, z)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=1..degree(p)))(b(n, 0, 1)):
seq(T(n), n=1..14);  # Alois P. Heinz, Nov 16 2019

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x==0, t,
     b[x-1, y+1, z] + Expand[b[x-1, y-1, 1]*t] + b[x-1, y, z]]];
T[n_] := CoefficientList[b[n, 0, 1]/z, z];
Array[T, 14] // Flatten (* Jean-François Alcover, Feb 14 2021, after Alois P. Heinz *)

G.f. G = G(t, z) satisfies G = z*(t+G)*(1+z+z*G).

A132814 A007318^(-1) * A132813.

Original entry on oeis.org

1, 0, 2, 0, 2, 3, 0, 0, 9, 4, 0, 0, 6, 24, 5, 0, 0, 0, 40, 50, 6, 0, 0, 0, 20, 150, 90, 7, 0, 0, 0, 0, 175, 420, 147, 8, 0, 0, 0, 0, 70, 840, 980, 224, 9, 0, 0, 0, 0, 0, 756, 2940, 2016, 324, 10, 0, 0, 0, 0, 0, 252, 4410, 8400, 3780, 450, 11

Offset: 0

Gary W. Adamson, Sep 01 2007

Row sums = A005773 starting (1, 2, 5, 13, 35, 96, ...).

			First few rows of the triangle:
  1;
  0, 2;
  0, 2, 3;
  0, 0, 9,  4;
  0, 0, 6, 24,   5;
  0, 0, 0, 40,  50,  6;
  0, 0, 0, 20, 150, 90, 7;
  ...

Cf. A132813, A005773.

tabl(nn) = {t007318 = matrix(nn, nn, n, k, binomial(n-1, k-1)); t132813 = matrix(nn, nn, n, k, binomial(n-1, k-1)*binomial(n, k-1)); t132814 = t007318^(-1)*t132813; for (n=1, nn, for (k=1, n, print1(t132814[n, k], ", ");););} \\ Michel Marcus, Feb 12 2014

Inverse binomial transform of A132813.

More terms from Michel Marcus, Feb 12 2014

A132893 Triangle read by rows: T(n,k) is the number of paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., left factors of Motzkin paths) and having k peaks (i.e., UDs), 0 <= k <= floor(n/2).

Original entry on oeis.org

1, 2, 4, 1, 9, 4, 21, 13, 1, 50, 40, 6, 121, 118, 27, 1, 296, 340, 106, 8, 730, 965, 381, 46, 1, 1812, 2708, 1296, 220, 10, 4521, 7535, 4241, 935, 70, 1, 11328, 20828, 13482, 3676, 395, 12, 28485, 57266, 41916, 13658, 1940, 99, 1

Offset: 0

Emeric Deutsch, Oct 08 2007

Row n has 1 + floor(n/2) terms.

Row sums yield A005773.

			T(3,1)=4 because we have HUD, UDH, UDU and UUD.
Triangle starts:
    1;
    2;
    4,   1;
    9,   4;
   21,  13,   1;
   50,  40,   6;
  121, 118,  27,   1;

Alois P. Heinz, Rows n = 0..200, flattened
Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

Cf. A005773, A091964, A132894.

G:=((-1+3*z-z^2+t*z^2+sqrt((1+z+z^2-t*z^2)*(1-3*z+z^2-t*z^2)))*1/2)/(z*(1-3*z+z^2-t*z^2)): Gser:=simplify(series(G,z=0,15)): for n from 0 to 12 do P[n]:=sort(coeff(Gser,z,n)) end do: for n from 0 to 12 do seq(coeff(P[n],t,j), j=0..floor((1/2)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(y<0, 0,
     `if`(x=0, 1, b(x-1, y, 1)+b(x-1, y-1, 1)*t+b(x-1, y+1, z))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Feb 01 2019

b[x_, y_, t_] := b[x, y, t] = Expand[If[y < 0, 0, If[x == 0, 1, b[x - 1, y, 1] + b[x - 1, y - 1, 1]*t + b[x - 1, y + 1, z]]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]] @ b[n, 0, 1];
T /@ Range[0, 15] // Flatten (* Jean-François Alcover, Oct 06 2019, after Alois P. Heinz *)

T(n,0) = A091964(n).
Sum_{k=0..floor(n/2)} k*T(n,k) = A132894(n-1).
G.f.: G = G(t,z) satisfies z(1 - 3z + z^2 - tz^2)G^2 + (1 - 3z + z^2 - tz^2)G - 1 = 0 (see the Maple program for the explicit expression of G).

A136787 Triangle read by rows: A107131 * A000012.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 4, 4, 4, 1, 9, 9, 9, 7, 1, 21, 21, 21, 21, 11, 1, 51, 51, 51, 51, 46, 16, 1, 127, 127, 127, 127, 127, 92, 22, 1, 323, 323, 323, 323, 323, 309, 169, 29, 1, 835, 835, 835, 835, 835, 835, 709, 289, 37, 1

Offset: 1

Gary W. Adamson, Jan 21 2008

Row sums = A005773 starting (1, 2, 5, 13, 35, 96, 267, ...).
Leftmost column = A001006: (1, 1, 2, 4, 9, 21, 51, ...).
A136788 = A000012 * A107131.

			First few rows of the triangle:
    1;
    1,   1;
    2,   2,   1;
    4,   4,   4,   1;
    9,   9,   9,   7,   1;
   21,  21,  21,  21,  11,  1;
   51,  51,  51,  51,  46, 16,  1;
  127, 127, 127, 127, 127, 92, 22, 1;
  ...

Cf. A005773, A001006, A136788.

A107131 * A000012 as infinite lower triangular matrices.

A239101 Riordan array read by rows, corresponding to array in A180562.

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 10, 5, 2, 1, 26, 13, 6, 2, 1, 70, 35, 16, 7, 2, 1, 192, 96, 45, 19, 8, 2, 1, 534, 267, 126, 56, 22, 9, 2, 1, 1500, 750, 357, 160, 68, 25, 10, 2, 1, 4246, 2123, 1016, 463, 198, 81, 28, 11, 2, 1, 12092, 6046, 2907, 1337, 586, 240, 95, 31

Offset: 0

N. J. A. Sloane, Mar 25 2014

Take lower triangle of square array in A180562, read from right to left.
Row sums are in A225034. - Philippe Deléham, Mar 25 2014
Riordan array (f(x), (f(x)-1)/(2*f(x))) where f(x) = sqrt((1+x)/(1-3*x)). - Philippe Deléham, Mar 25 2014

			Triangle begins:
1
2 1
4 2 1
10 5 2 1
26 13 6 2 1
70 35 16 7 2 1
192 96 45 19 8 2 1
...
192 = 2*96, 96 = 70 - 35 + 16 + 45, 45 = 35 - 16 + 7 + 19, etc. - _Philippe Deléham_, Mar 25 2014
Production matrix is:
2, 1
0, 0, 1
2, 1, 0, 1
2, 1, 1, 0, 1
2, 1, 1, 1, 0, 1
2, 1, 1, 1, 1, 0, 1
2, 1, 1, 1, 1, 1, 0, 1
2, 1, 1, 1, 1, 1, 1, 0, 1
... _Philippe Deléham_, Sep 15 2014

D. Baccherini, D. Merlini, R. Sprugnoli, Binary words excluding a pattern and proper Riordan arrays, Discrete Math. 307 (2007), no. 9-10, 1021--1037. MR2292531 (2008a:05003).

Cf. A180562.

Cf. T(n,0) = A025565(n+1), T(n+1,1) = A005773(n+1), T(n+2,2) = A005717(n+1), A225034 (Row sums). - Philippe Deléham, Mar 25 2014

T(0,0) = 1, T(n,0) = 2*T(n,1) for n>0, T(n,k) = T(n-1,k-1) - T(n-1,k) + T(n-1,k+1) + T(n,k+1) for k>0, T(n,k) = 0 if k<0 or if k>n. - Philippe Deléham, Mar 25 2014

More terms from Philippe Deléham, Mar 25 2014

A300665 Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.

Original entry on oeis.org

1, 3, 15, 75, 391, 2065, 11091, 60215, 330003, 1820869, 10103153, 56313047, 315071801, 1768489771, 9953853677, 56158682949, 317505199769, 1798402412539

Offset: 0

Ricardo Bittencourt, Mar 10 2018

All terms are odd.

			For n=2, the a(2)=15 paths are:
.
.    0 . .     0 . .     0 . .     0 2 .     0 . .
.    |         |         |         |/         \
.    1 . .     1 . .     1-2 .     1 . .     2-1 .
.    |          \
.    2 . .     . 2 .     . . .     . . .     . . .
.
.    0 . .     0 . .     0 . .     0 . .     0 . 2
.     \         \         \         \         \ /
.    . 1 .     . 1 .     . 1 .     . 1-2     . 1 .
.     /          |          \
.    2 . .     . 2 .     . . 2     . . .     . . .
.
.    0 2 .     0-1 .     0-1 .     0-1 .     0-1-2
.     \|        /          |          \
.    . 1 .     2 . .     . 2 .     . . 2     . . .
.
.    . . .     . . .     . . .     . . .     . . .

Ricardo Bittencourt, C++ code, GitHubGist.
Ricardo Bittencourt, Go code, GitHubGist.
OEIS Wiki: Self-avoiding walks

A038373 is the same process, but using only horizontal and vertical moves.

Cf. A005773, A272469, A272763, A272773.

Go
```
(see GitHubGist link)
```

next[x_]:=Map[x + #&, Tuples[{-1, 0, 1}, 2]]
valid[s_]:=Select[next[s[[-1]]], 0<=#[[1]] && 0<=#[[2]] && FreeQ[s,#] &]
nextpath[p_]:=Outer[Append,{p},valid[p],1]
iterate[p_]:=Flatten[Map[nextpath, p], 2]
Table[Length[Nest[iterate, {{{0,0}}}, n-1]], {n,1,7}]

a(n) = A272469(n) + 2*A005773(n+1) - 1 for n > 0. - Andrey Zabolotskiy, Mar 12 2018

A305560 Expansion of Sum_{k>=0} binomial(k,floor(k/2))x^k/Product_{j=1..k} (1 - jx).

Original entry on oeis.org

1, 1, 3, 10, 39, 176, 893, 4985, 30229, 197452, 1379655, 10250087, 80558195, 666916238, 5795111845, 52691973136, 499969246647, 4938724595994, 50679201983653, 539209298355565, 5938139329609621, 67582179415195986, 793755139140445707, 9608367683839952732, 119730171975510540577

Offset: 0

Ilya Gutkovskiy, Jun 21 2018

nonn

Stirling transform of A001405.

Vaclav Kotesovec, Table of n, a(n) for n = 0..550
N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Stirling Transform

Cf. A001405, A005773, A064856, A305406.

a:= n-> add(binomial(j, floor(j/2))*Stirling2(n, j), j=0..n):
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 21 2018

nmax = 24; CoefficientList[Series[Sum[Binomial[k, Floor[k/2]] x^k/Product[1 - j x, {j, 1, k}], {k, 0, nmax}], {x, 0, nmax}], x]
nmax = 24; CoefficientList[Series[BesselI[0, 2 (Exp[x] - 1)] + BesselI[1, 2 (Exp[x] - 1)], {x, 0, nmax}], x] Range[0, nmax]!
Table[Sum[StirlingS2[n, k] Binomial[k, Floor[k/2]], {k, 0, n}], {n, 0, 24}]

E.g.f.: BesselI(0,2*(exp(x) - 1)) + BesselI(1,2*(exp(x) - 1)).

a(n) = Sum_{k=0..n} Stirling2(n,k)*binomial(k,floor(k/2)).

A330510 Triangle read by rows: T(n,k) is the number of ternary strings of length n+1 with k+1 indispensable digits and a nonzero leading digit, with 0 <= k <= n.

Original entry on oeis.org

2, 3, 3, 4, 10, 4, 5, 22, 22, 5, 6, 40, 70, 40, 6, 7, 65, 171, 171, 65, 7, 8, 98, 356, 534, 356, 98, 8, 9, 140, 665, 1373, 1373, 665, 140, 9, 10, 192, 1148, 3088, 4246, 3088, 1148, 192, 10, 11, 255, 1866, 6294, 11257, 11257, 6294, 1866, 255, 11

Offset: 0

Ji Young Choi, Dec 16 2019

A digit in a string is called indispensable if it is greater than the following digit or equal to the following digits which are eventually greater than the following digit. We also assume that there is an invisible digit 0 at the end of any string. For example, in 7233355548, the digits 7, 5, 5, 5, and 8 are indispensable.

T(n, k) is also the number of integers m where the length of ternary representation of m is n+k and the digit sum of the ternary representation of 2m is 2(k+1).

			Triangle begins
  2;
  3,   3;
  4,  10,   4;
  5,  22,  22,   5;
  6,  40,  70,  40,   6;
  7,  65, 171, 171,  65,   7;
  ...
There are 4 strings (100, 112, 120, 200) of length 3 with 1 indispensable digits and a nonzero leading digit.
There are 10 strings (101, 102, 110, 121, 122, 201, 202, 210, 212, 220) of length 3 with 2 indispensable digits are a nonzero leading digit.
There are 4 strings (111, 211, 221, 222) of length 3 with 3 indispensable digits and a nonzero leading digit.
Hence T(2,0)=4, T(2,1)=10, T(2,2)=4.

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
J. Y. Choi, Indispensable digits for digit sums, Notes Number Theory Discrete Math 25 (2019), pp. 40-48.
J. Y. Choi, Digit sums generalizing binomial coefficients, J. Integer Seq. 22 (2019), Article 19.8.3.

Cf. A005773, A330381, A027907.

A027907(n, k) = if(n<0, 0, polcoef((1 + x + x^2)^n, k));
T(n,k) = {A027907(n+1, 2*k+1) + A027907(n+1, 2*k+2) - A027907(n, 2*k+1) - A027907(n, 2*k+2)} \\ Andrew Howroyd, Dec 20 2019

T(n, k) = A330381(n+1, k+1) - A330381(n, k+1).

A344506 a(n) = [x^n] 2 / (1 - 7x + sqrt(1 - 2x - 3*x^2)).

Original entry on oeis.org

1, 4, 17, 73, 315, 1362, 5895, 25528, 110579, 479068, 2075683, 8993897, 38971621, 168871854, 731764089, 3170939841, 13740635787, 59542470588, 258016586955, 1118069698011, 4844962624953, 20994821090790, 90977510544237, 394235745437286, 1708354520308101

Offset: 0

Peter Luschny, May 23 2021

nonn

The Motzkin polynomials (coefficients in A064189) evaluated at x = 3.

The Motzkin polynomials evaluated at: x = 0 (A001006), x = 1 (A005773), x = 2 (A059738), x = 3 (this sequence).

Cf. A064189, A344507.

gf := 2 / (1 - 7*x + sqrt(1 - 2*x - 3*x^2)):
ser := series(gf, x, 27): seq(coeff(ser, x, n), n=0..25);
# Or:
rgf := (3*x^2 + x)/(13*x^2 + 7*x + 1):
subsop(1 = NULL, gfun:-seriestolist(series(rgf, x, 28), 'revogf'));

RecurrenceTable[{a[n] == (39 (2 - n) a[n - 3] - (17 n + 5) a[n - 2] + (19 n + 10) a[n - 1])/(3 n + 3), a[0] == 1, a[1] == 4, a[2] == 17}, a, {n, 0, 26}]

R. = PowerSeriesRing(QQ, default_prec=25)
f = (3*x^2 + x) / (13*x^2 + 7*x + 1)
f.reverse().shift(-1).list()

a(n) = [x^n] reverse((3*x^2 + x) / (13*x^2 + 7*x + 1)) / x.
a(n) = Sum_{k=0..n} 3^k*binomial(n, k)*hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4).
a(n) = (39*(2 - n)*a(n - 3) - (17*n + 5)*a(n - 2) + (19*n + 10)*a(n - 1))/(3*n + 3) for n >= 3.
a(n) ~ 8 * 13^n / 3^(n+2). - Vaclav Kotesovec, May 24 2021
G.f.: 1/(1 - 4*x - x^2/(1 - x - x^2/(1 - x - x^2/(1 - x - x^2/(1 - ...))))), a continued fraction. - Ilya Gutkovskiy, Nov 19 2021

cp's OEIS Frontend

A113408 Riordan array (1/(1-x^2-x^4*c(x^4)),x*c(x^2)), c(x) the g.f. of A000108.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

Formula

A114690 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n and having k weak ascents (1 <= k <= ceiling(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A132814 A007318^(-1) * A132813.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A132893 Triangle read by rows: T(n,k) is the number of paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., left factors of Motzkin paths) and having k peaks (i.e., UDs), 0 <= k <= floor(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A136787 Triangle read by rows: A107131 * A000012.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A239101 Riordan array read by rows, corresponding to array in A180562.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A300665 Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Go

Mathematica

Formula

A305560 Expansion of Sum_{k>=0} binomial(k,floor(k/2))*x^k/Product_{j=1..k} (1 - j*x).

Views

Author

A113408 Riordan array (1/(1-x^2-x^4c(x^4)),xc(x^2)), c(x) the g.f. of A000108.

A305560 Expansion of Sum_{k>=0} binomial(k,floor(k/2))x^k/Product_{j=1..k} (1 - jx).

A344506 a(n) = [x^n] 2 / (1 - 7x + sqrt(1 - 2x - 3*x^2)).