A064189 -id:A064189 - cp's OEIS frontend

A344503 a(n) = Sum_{k=0..n} (-1)^(n-k)binomial(n, k)^2hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4).

1, 0, -1, 3, 0, -5, 15, 0, -28, 84, 0, -165, 495, 0, -1001, 3003, 0, -6188, 18564, 0, -38760, 116280, 0, -245157, 735471, 0, -1562275, 4686825, 0, -10015005, 30045015, 0, -64512240, 193536720, 0, -417225900, 1251677700, 0, -2707475148, 8122425444, 0, -17620076360

Offset: 0

Peter Luschny, May 23 2021

sign

Inverse binomial convolution of the Motzkin numbers.

Cf. A064189 (Motzkin numbers), A005809, A025174, A344502.

a := n -> add((-1)^(n - k)*binomial(n, k)^2*hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4), k = 0..n): seq(simplify(a(n)), n = 0..41);

a(3*n) = binomial(3*n, n) (A005809).
a(3*n - 1) = -binomial(3*n - 1, n - 1) (A025174).
a(3*n - 2) = 0.
Conjecture D-finite with recurrence -18*(2*n+1) *(2*n-1) *(n+1) *a(n) +2*(-36*n^3+554*n^2-1128*n+27) *a(n-1) +6*(-12*n^3-188*n^2+1235*n-1618) *a(n-2) +9*(54*n^3-27*n^2-183*n+320) *a(n-3) +54*(n-3) *(9*n^2-125*n+75) *a(n-4) +81 *(n-3) *(n-4) *(6*n+127) *a(n-5)=0. - R. J. Mathar, Nov 02 2021

A344567 A(n, k) = [x^k] 2 / (1 - (2n - 1)x + sqrt(1 - 2x - 3x^2)). The number of n-colored Motzkin arcs of length k. Array read by ascending antidiagonals, n >= 0 and k >= 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 4, 3, 1, 4, 10, 13, 9, 6, 1, 5, 17, 34, 35, 21, 15, 1, 6, 26, 73, 117, 96, 51, 36, 1, 7, 37, 136, 315, 405, 267, 127, 91, 1, 8, 50, 229, 713, 1362, 1407, 750, 323, 232, 1, 9, 65, 358, 1419, 3741, 5895, 4899, 2123, 835, 603

Offset: 0

Peter Luschny, May 24 2021

Given a sequence a(n), we call the sequence b(n) Cameron's inverse of a, or, as dubbed by Sloane, INVERTi(a) (see the link 'Transforms' in the footer of the page), if 1 + Sum_{n>=1} a(n)*x^n = 1/(1 - Sum_{n>=1} b(n)*x^n).
Iterating this transform starting from A344506 we get:
  a = A344506.
  INVERTi(a) = A059738.
  INVERTi(INVERTi(a)) = A005773.
  INVERTi(INVERTi(INVERTi(a))) = A001006, Motzkin numbers.
  INVERTi(INVERTi(INVERTi(INVERTi(a)))) = A005043.
  INVERTi(INVERTi(INVERTi(INVERTi(INVERTi(a))))) = A344507.
The sequences generated in this manner correspond to the evaluation of the Motzkin polynomials (coefficients in A064189) at x = 3, 2, 1, 0, -1, -2. In terms of ordinary generating functions we have a ZZ-indexed sequence of sequences which general form is given by the formula in the name.
A "Motzkin path of length n and height k" is an integer lattice path from (0, 0) to (n, k) remaining weakly above the x-axis and consisting of steps in {U, L, D}. These acronyms stand for the steps Up = (1,1), Level = (1,0), and Down = (1, -1). An "n-colored Motzkin arc of length k" is a Motzkin path of length k and height 0 where each Level step of height 0 has one of n colors. A(n, k) is the number of n-colored Motzkin arcs of length k. The Motzkin numbers are M(k) = A(1, k).

			Array begins at n = 0, row for n = -1 added for illustration:
n\k  0   1    2     3      4       5        6         7  ... [Sequence Triangle]
--------------------------------------------------------------------------------
[-1] 1, -1,   2,   -2,     5,     -3,      15,        3, ...  [A344507]
[ 0] 1,  0,   1,    1,     3,      6,      15,       36, ...  [A005043, A089942]
[ 1] 1,  1,   2,    4,     9,     21,      51,      127, ...  [A001006, A064189]
[ 2] 1,  2,   5,   13,    35,     96,     267,      750, ...  [A005773, A038622]
[ 3] 1,  3,  10,   34,   117,    405,    1407,     4899, ...  [A059738, A126954]
[ 4] 1,  4,  17,   73,   315,   1362,    5895,    25528, ...  [A344506]
[ 5] 1,  5,  26,  136,   713,   3741,   19635,   103071, ...
[ 6] 1,  6,  37,  229,  1419,   8796,   54531,   338082, ...
[ 7] 1,  7,  50,  358,  2565,  18381,  131727,   944035, ...
[ 8] 1,  8,  65,  529,  4307,  35070,  285567,  2325324, ...
.
Triangle starts:
[0] 1;
[1] 1, 0;
[2] 1, 1,  1;
[3] 1, 2,  2,   1;
[4] 1, 3,  5,   4,   3;
[5] 1, 4, 10,  13,   9,    6;
[6] 1, 5, 17,  34,  35,   21,   15;
[7] 1, 6, 26,  73, 117,   96,   51,  36;
[8] 1, 7, 37, 136, 315,  405,  267, 127,  91;
[9] 1, 8, 50, 229, 713, 1362, 1407, 750, 323, 232.
.
Number of colors = 2, length = 4  ->  35.
.
      /\      _ _
     /  \    /   \   /\/\      3 x 1
.    _         _
    / \_     _/ \              2 x 2
.
    /\_ _   _ _/\   _/\_       3 x 4
.
    _ _ _ _                    1 x 16
.
Number of colors = 4, length = 2  ->  17.
.
    /\                         1 x 1
.
    _ _                        1 x 16

Martin Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675.
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discrete Mathematics, Vol. 204, No. 1-3 (1999), 73-112.
Isaac DeJager, Madeleine Naquin, Frank Seidl, Paul Drube, Colored Motzkin Paths of Higher Order, Journal of Integer Sequences, Vol. 24 (2021)

Cf. A064189, A097609, A344506, A059738, A005773, A001006, A005043, A344507.

Cf. triangles: A089942, A064189, A038622, A126954.

Arow := proc(n, len) option remember;
2 / (1 - (2*n - 1)*x + sqrt(1 - 2*x - 3*x^2));
seq(coeff(series(%, x, len+2), x, k), k = 0..len) end:
T := (n, k) -> Arow(n-k, k+1)[k+1]:
for n from 0 to 9 do Arow(n, 7) od; # prints array
for n from 0 to 9 do seq(T(n, k), k=0..n) od; # prints triangle
# Alternative via series reversion:
for n from -1 to 6 do  # print the array starting from n = -1
rgf := x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1):
subsop(1 = NULL, gfun:-seriestolist(series(rgf, x, 18), 'revogf')) od;
# Via recursively defined polynomials:
p := proc(n, k) option remember;
if n = k then 1 elif k < 0 or n < 0 or k > n then 0 elif k = 0 then x*p(n-1, 0) + p(n-1, 1) else p(n-1, k-1) + p(n-1, k) + p(n-1, k+1) fi end:
A := (n, k) -> subs(x = n, p(k, 0)):
for n from 0 to 8 do lprint(seq(A(n, k), k = 0..9)) od;
# Computing the columns:
Acol := proc(k, len) seq(subs(x = n, p(k, 0)), n = 0..len) end:
for k from 0 to 6 do Acol(k, 9) od;

Unprotect[Power]; 0^0 := 1;
A[n_, k_] := Sum[(n-1)^j Binomial[k, j] Hypergeometric2F1[(j - k)/2, (j - k + 1)/2, j + 2, 4], {j, 0, k}]; Table[A[n, k], {n, 0, 6}, {k, 0, 8}]

F(n) = {x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1)}
M(n,m=n) = {Mat(vectorv(n, i, Vec(serreverse(F(i-1) + O(x*x^m)))))}
{ my(A=M(8)); for(n=1, #A, print(A[n, ])) } \\ Andrew Howroyd, May 27 2021

def Arow(n, len):
    R. = PowerSeriesRing(QQ, default_prec=len)
    f = x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1)
    return f.reverse().shift(-1).list()
for n in (0..8): print(Arow(n,10))

A(n, k) = Sum_{j=0..n} (k - 1)^j*binomial(n, j)*hypergeom([(j - n)/2, (j - n + 1)/2], [j + 2], 4).
Arow(n) = [x^n] reverse(x*((n-1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n-1)*x + 1)) / x.
Computationally more elementary is the following procedure: Let P_n(x) be polynomials defined recursively by P_n(x) = p(n, 0) where p(n, k) = 0 if k < 0 or n < 0 or k > n, p(n, n) = 1, p(n, 0) = x*p(n-1, 0) + p(n-1, 1), and in all other cases p(n, k) = p(n-1, k-1) + p(n-1, k) + p(n-1, k+1). Then A(n, k) = P_k(n).
The coefficients of these polynomials are in A097609. Thus the columns of the array can be calculated as: Acol(k) = [P_k(n) for n >= 0].

A106489 Triangle read by rows: T(n,k) is the number of short bushes with n edges and having the leftmost leaf at height k (a short bush is an ordered tree with no nodes of outdegree 1).

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 9, 5, 1, 21, 12, 3, 51, 30, 9, 1, 127, 76, 25, 4, 323, 196, 69, 14, 1, 835, 512, 189, 44, 5, 2188, 1353, 518, 133, 20, 1, 5798, 3610, 1422, 392, 70, 6, 15511, 9713, 3915, 1140, 230, 27, 1, 41835, 26324, 10813, 3288, 726, 104, 7, 113634, 71799, 29964

Offset: 2

Emeric Deutsch, May 29 2005

Basically, the mirror image of A020474. Row n has floor(n/2) terms (first row is row 2). Row sums yield the Riordan numbers (A005043). Column 1 yields the Motzkin numbers (A001006); column 2 yields A002026; column 3 yields A005322; column 4 yields A005323; column 4 yields A005324; column 5 yields A005325; column 6 yields A005326.

T(n,k) is the number of Riordan paths (Motzkin paths with no flatsteps on the x-axis) with k returns to the x-axis. For example, T(6,2) = 5 counts UDUFFD, UDUUDD, UFDUFD, UFFDUD, UUDDUD where U = (1,1) is an upstep, F = (1,0) is a flatstep, and D = (1,-1) is a downstep. - David Callan, Dec 12 2021

			Column 1 yields the Motzkin numbers: indeed, if from each short bush, having leftmost leaf at height 1, we drop the leftmost edge, then we obtain the so-called bushes, known to be counted by the Motzkin numbers.
Triangle begins:
   1;
   1;
   2,  1;
   4,  2;
   9,  5,  1;
  21, 12,  3;
  51, 30,  9,  1.

F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999), 73-112.
Sen-Peng Eu, Shu-Chung Liu, and Yeong-Nan Yeh, Taylor expansions for Catalan and Motzkin numbers, Advances in Applied Mathematics 29, Issue 3 (2002), 345-357 (see p. 352).

Cf. A020474, A005043, A001006, A002026, A005322, A005323, A005324, A005325, A005326, A064189.

S:=1/2/(z+z^2)*(1+z-sqrt(1-2*z-3*z^2)): G:=simplify(t*z^2*S/(1-z*S-t*z^2*S)): Gserz:=simplify(series(G,z=0,19)): for n from 2 to 17 do P[n]:=sort(coeff(Gserz,z^n)) od: for n from 2 to 17 do seq(coeff(P[n],t^k),k=1..floor(n/2)) od; # yields sequence in triangular form

(* To generate the sequence *)
CoefficientList[CoefficientList[Series[(1-t-2xt^2-Sqrt[1-2t-3t^2])/(2t^2(1-x+xt+x^2t^2)), {t,0,10}], t], x] // Flatten
(* To generate the triangle *)
CoefficientList[Series[(1-t-2xt^2-Sqrt[1-2t-3t^2])/(2t^2(1-x+xt+x^2t^2)), {t, 0, 10}], {t, x}] // MatrixForm
Table[If[n < 2 k, 0, GegenbauerC[n-2k,-n+k-1,-1/2](k+1)/(n-k+1)], {n,0,10}, {k,0,5}] // MatrixForm
(* Emanuele Munarini, Feb 10 2018 *)

G.f.: tz^2*S/(1 - zS - tz^2*S), where S = S(z) = (1 + z - sqrt(1 - 2z - 3z^2))/(2z(1+z)) is the g.f. of the short bushes (the Riordan numbers; A005043).
a(n,k) = T(n-k+1, n-2*k)*(k+1)/(n-k+1), for n >= 2k, where T(n,k) = A027907(n,k) are the trinomial coefficients. - Emanuele Munarini, Feb 10 2018
The rows are the antidiagonals of the Motzkin triangle A064189. - Peter Luschny, Feb 01 2025

A291083 Irregular triangle read by rows: T(n,m) = number of lattice paths of type A^Q terminating at point (n, m).

Original entry on oeis.org

1, 1, 4, 5, 3, 1, 21, 30, 25, 14, 5, 1, 127, 196, 189, 133, 70, 27, 7, 1, 835, 1353, 1422, 1140, 726, 369, 147, 44, 9, 1, 5798, 9713, 10813, 9438, 6765, 4037, 2002, 814, 264, 65, 11, 1, 41835, 71799, 83304, 77220, 60060, 39897, 22737, 11076, 4563, 1560, 429, 90, 13, 1

Offset: 0

N. J. A. Sloane, Aug 19 2017

			Triangle begins:
1,1,
4,5,3,1,
21,30,25,14,5,1,
127,196,189,133,70,27,7,1,
835,1353,1422,1140,726,369,147,44,9,1,
5798,9713,10813,9438,6765,4037,2002,814,264,65,11,1,
41835,71799,83304,77220,60060,39897,22737,11076,4563,1560,429,90,13,1,
310572,542895,649845,630084,520455,373581,234780,129285,62127,25830,9163,2715,650,119,15,1,
...

Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.

First column is A099250.

Cf. A064189.

A344395 a(n) = binomial(4n - 1, 2n - 1)hypergeom([-n, -n + 1/2], [2n + 1], 4).

Original entry on oeis.org

1, 5, 133, 4037, 129285, 4266830, 143567173, 4896136845, 168640510725, 5853000551090, 204368928058958, 7170955214476509, 252638095187722437, 8931025389858103602, 316640855103349347725, 11254413331736554364987, 400893874585938826203909, 14307778459379093347171266

Offset: 0

Peter Luschny, May 19 2021

nonn

Related to the Motzkin triangle A064189 counting certain lattice paths.

Cf. A064189, A344394, A327871.

alias(C=binomial):
a := n -> `if`(n = 0, 1, add(C(4*n - 1, j)*(C(4*n - 1 - j, j + 2*n - 1) - C(4*n - 1 - j, j + 2*n + 1)), j = 0..4*n-1)): seq(a(n), n = 0..17);

a[n_] := Binomial[4 n - 1, 2 n - 1] Hypergeometric2F1[-n, -n + 1/2, 2 n + 1, 4];
Table[a[n], {n, 0, 19}]

a(n) = Sum_{j=0..4*n-1} C(4*n-1, j)*(C(4*n-1-j, j+2*n-1) - C(4*n-1-j, j+2*n+1)) for n >= 1.
a(n) = A064189(4*n - 1, 2*n - 1) for n >= 1.
a(n) = A344394(4*n - 1) for n >= 1.
a(n) ~ sqrt(1014 + 156*sqrt(13)) * (13688 + 3640*sqrt(13))^n / (52 * sqrt(Pi*n) * 3^(6*n+1)). - Vaclav Kotesovec, Feb 18 2024
D-finite with recurrence +9*n*(6*n-1)*(3*n-1)*(3835115277622*n -6057563812695) *(2*n-1)*(3*n-2) *(6*n-5)*a(n) +2*(776430552534185648*n^7 -13254965233720706112*n^6 +77698256107321929944*n^5 -233839293644869788720*n^4 +406279253239920624227*n^3 -412808144693534857728*n^2 +228023561050132883751*n -52874097275943488160)*a(n-1) -108*(4*n-5)*(4*n-7) *(51631651831183544*n^5 -528937515408392660*n^4 +2125620894576233062*n^3 -4194554621940993427*n^2 +4055650255694760927*n -1531029729082241880)*a(n-2) +402408*(4*n-11)*(n-2) *(4*n-5)*(4*n-9)*(330342177838*n -391995025711)*(2*n-5) *(4*n-7)*a(n-3)=0. - R. J. Mathar, Mar 25 2024

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

Original entry on oeis.org

0, 1, 6, 26, 100, 361, 1254, 4245, 14108, 46247, 149998, 482412, 1540880, 4893859, 15468910, 48696930, 152764452, 477771447, 1490245302, 4637349186, 14400224496, 44632551567, 138101593398, 426658380621, 1316306945952, 4055853282741, 12482506508174, 38375733088400

Offset: 0

Peter Luschny, May 23 2021

nonn

Motzkin transform of the squares.

Cf. A064189 (Motzkin numbers).

gf := ((x - 1)/sqrt(4/(x + 1) - 3) + x + 1)/(2*x*(3*x - 1)):
ser := series(gf, x, 30): seq(coeff(ser, x, n), n=0..27);

a(n) = Sum_{k=0..n} k^2*binomial(n, k)*hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4).
a(n) ~ 4 * 3^(n - 1/2) * sqrt(n/Pi) * (1 - sqrt(3*Pi/n)/2). - Vaclav Kotesovec, May 24 2021
D-finite with recurrence -(n+1)*(2*n-3)*a(n) +(10*n^2-5*n-12)*a(n-1) -3*(2*n+5)*(n-1)*a(n-2) -9*(2*n-1)*(n-2)*a(n-3)=0. - R. J. Mathar, Mar 06 2022

A344566 T(n, k) = (-1)^(n - k)binomial(n - 1, k - 1)hypergeom([-(n - k)/2, -(n - k - 1)/2], [1 - n], 4). Triangle read by rows, T(n, k) for 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, -1, 1, 0, 0, -2, 1, 0, 1, 1, -3, 1, 0, -1, 2, 3, -4, 1, 0, 0, -4, 2, 6, -5, 1, 0, 1, 2, -9, 0, 10, -6, 1, 0, -1, 3, 9, -15, -5, 15, -7, 1, 0, 0, -6, 3, 24, -20, -14, 21, -8, 1, 0, 1, 3, -18, -6, 49, -21, -28, 28, -9, 1

Offset: 0

Peter Luschny, May 23 2021

The inverse of the Riordan array for directed animals A122896. Without the first column (1, 0, 0, ...) the inverse of the Motzkin triangle A064189.

			Triangle starts:
[0] 1;
[1] 0,  1;
[2] 0, -1,  1;
[3] 0,  0, -2,  1;
[4] 0,  1,  1, -3,   1;
[5] 0, -1,  2,  3,  -4,   1;
[6] 0,  0, -4,  2,   6,  -5,   1;
[7] 0,  1,  2, -9,   0,  10,  -6, 1;
[8] 0, -1,  3,  9, -15,  -5,  15, -7,  1;
[9] 0,  0, -6,  3,  24, -20, -14, 21, -8, 1.

A117569 (row sums).

Cf. A122896, A064189.

T := (n,k) -> (-1)^(n-k)*binomial(n-1,k-1)*hypergeom([-(n-k)/2, -(n-k-1)/2], [1-n], 4): seq(seq(simplify(T(n, k)), k=0..n), n = 0..10);

# uses[riordan_array from A256893]
riordan_array(1, x / (1 + x + x^2), 10)

Riordan_array (1, x / (1 + x + x^2)).

cp's OEIS Frontend

A307789 Number of valid hook configurations of permutations of [n] that avoid the patterns 231 and 1243.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A344503 a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)^2*hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula

A344567 A(n, k) = [x^k] 2 / (1 - (2*n - 1)*x + sqrt(1 - 2*x - 3*x^2)). The number of n-colored Motzkin arcs of length k. Array read by ascending antidiagonals, n >= 0 and k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

SageMath

Formula

A106489 Triangle read by rows: T(n,k) is the number of short bushes with n edges and having the leftmost leaf at height k (a short bush is an ordered tree with no nodes of outdegree 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A291083 Irregular triangle read by rows: T(n,m) = number of lattice paths of type A^Q terminating at point (n, m).

Views

Author

Keywords

Examples

Links

Crossrefs

A344395 a(n) = binomial(4*n - 1, 2*n - 1)*hypergeom([-n, -n + 1/2], [2*n + 1], 4).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula

A344566 T(n, k) = (-1)^(n - k)*binomial(n - 1, k - 1)*hypergeom([-(n - k)/2, -(n - k - 1)/2], [1 - n], 4). Triangle read by rows, T(n, k) for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

SageMath

A344503 a(n) = Sum_{k=0..n} (-1)^(n-k)binomial(n, k)^2hypergeom([(k-n)/2, (k-n+1)/2], [k+2], 4).

A344567 A(n, k) = [x^k] 2 / (1 - (2n - 1)x + sqrt(1 - 2x - 3x^2)). The number of n-colored Motzkin arcs of length k. Array read by ascending antidiagonals, n >= 0 and k >= 0.

A344395 a(n) = binomial(4n - 1, 2n - 1)hypergeom([-n, -n + 1/2], [2n + 1], 4).

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

A344566 T(n, k) = (-1)^(n - k)binomial(n - 1, k - 1)hypergeom([-(n - k)/2, -(n - k - 1)/2], [1 - n], 4). Triangle read by rows, T(n, k) for 0 <= k <= n.