A115717 -id:A115717 - cp's OEIS frontend

A115718 Inverse of number triangle A115717; a divide-and-conquer related triangle.

1, 0, 1, -3, 1, 1, 0, 0, 0, 1, -3, -3, 1, 1, 1, 0, 0, 0, 0, 0, 1, -3, -3, -3, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, -3, -3, -3, -3, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -3, -3, -3, -3, -3, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -3, -3, -3, -3, -3, -3, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Paul Barry, Jan 29 2006

Product of A115713 and (1/(1-x), x).
Row sums are 1,1,-1,1,-3,1,-5,1,-7,1, ... with g.f. (1+x-3*x^2-x^3)/(1-x^2)^2.
Row sums of inverse are A115716.

			Triangle begins
   1;
   0,  1;
  -3,  1,  1;
   0,  0,  0,  1;
  -3, -3,  1,  1,  1;
   0,  0,  0,  0,  0,  1;
  -3, -3, -3,  1,  1,  1,  1;
   0,  0,  0,  0,  0,  0,  0,  1;
  -3, -3, -3, -3,  1,  1,  1,  1,  1;
   0,  0,  0,  0,  0,  0,  0,  0,  0,  1;
  -3, -3, -3, -3, -3,  1,  1,  1,  1,  1,  1;
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1;
  -3, -3, -3, -3, -3, -3,  1,  1,  1,  1,  1,  1,  1;
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1;
  -3, -3, -3, -3, -3, -3, -3,  1,  1,  1,  1,  1,  1,  1,  1;

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

Cf. A115713, A115716, A115717, A237420.

T[n_, k_]:= If[OddQ[n], If[kG. C. Greubel, Nov 29 2021 *)

def A115718(n,k):
    if (n%2==0): return 0 if (kA115718(n,k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Nov 29 2021

From G. C. Greubel, Nov 29 2021: (Start)
T(2*n, k) = -3 if (k < n/2) otherwise 1.
T(2*n+1, k) = 0 if (k < n) otherwise 1.
Sum_{k=0..n} T(n, k) = (1/2)*(2 + (1 + (-1)^n)*n) = 1 + A237420(n). (End)

A115716 A divide-and-conquer sequence.

Original entry on oeis.org

1, 1, 3, 1, 3, 1, 11, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 683, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1

Offset: 0

Paul Barry, Jan 29 2006

			G.f. = 1 + x + 3*x^2 + x^3 + 3*x^4 + x^5 + 11*x^6 + x^7 + 3*x^8 + x^9 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..16381
R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences , arXiv:math/0307027 [math.CO], 2003.

Partial sums are A032925.
Row sums of number triangle A115717.
Bisection: A276390.
Cf. A007583, A081294, A091090.
See A276391 for a closely related sequence.

a:= proc(n) option remember; `if`(n=0, 1,
      `if`(n::odd, 1, 4*a(n/2-1)-1))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Sep 07 2016

a[n_] := a[n] = If[n == 0, 1, If[OddQ[n], 1, 4*a[n/2-1]-1]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jan 25 2017, after Alois P. Heinz *)

{a(n) = if( n<1, n==0, n%2, 1, 4 * a(n/2-1) - 1)}; /* Michael Somos, Sep 07 2016 */

The g.f. G(x) satisfies G(x)-4*x^2*G(x^2)=(1+2*x)/(1+x). - Argument and offset corrected by Bill Gosper, Sep 07 2016
G.f.: 1/(1-x) + Sum_{k>=0} ((4^k-0^k)/2) *x^(2^(k+1)-2) /(1-x^(2^k)). - corrected by R. J. Mathar, Sep 07 2016
a(n)=A007583(A091090(n+1)-1). - Adapted to new offset by R. J. Mathar, Sep 07 2016
a(0) = 1, a(2*n + 1) = 1 for n>=0. a(2*n + 2) = 4*a(n) - 1 for n>=0. - Michael Somos, Sep 07 2016

A114583 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n and having k UHD's, where U=(1,1),H=(1,0),D=(1,-1) (0<=k<=floor(n/3)).

Original entry on oeis.org

1, 1, 2, 3, 1, 7, 2, 15, 6, 36, 14, 1, 85, 39, 3, 209, 102, 12, 517, 280, 37, 1, 1303, 758, 123, 4, 3312, 2085, 381, 20, 8510, 5730, 1194, 76, 1, 22029, 15849, 3657, 295, 5, 57447, 43914, 11187, 1056, 30, 150709, 122090, 33903, 3734, 135, 1, 397569, 340104

Offset: 0

Emeric Deutsch, Dec 09 2005

Row n contains 1+floor(n/3) terms. Row sums are the Motzkin numbers (A001006). Column 1 yields A114584. Sum(k*T(n,k),k=0..floor(n/3))=A005717(n-2).

			T(5,1)=6 because we have HH(UHD), UD(UHD), (UHD)HH, (UHD)UD, H(UHD)H and U(UHD)D, where U=(1,1),H=(1,0),D=(1,-1) (the UHD's are shown between parentheses).
Triangle begins:
   1;
   1;
   2;
   3,  1;
   7,  2;
  15,  6;
  36, 14, 1;
  ...

Alois P. Heinz, Rows n = 0..300, flattened
Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.
Zhuang, Yan. A generalized Goulden-Jackson cluster method and lattice path enumeration, Discrete Mathematics 341.2 (2018): 358-379. Also arXiv: 1508.02793v2.

Cf. A001006, A114584, A115717.

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

CoefficientList[#, t]& /@ CoefficientList[(1 - z - t z^3 + z^3 - Sqrt[(1 - 3z + z^3 - t z^3)(1 + z + z^3 - t z^3)])/2/z^2 + O[z]^17, z] // Flatten (* Jean-François Alcover, Aug 07 2018 *)

G.f.=G=G(t, z) satisfies G=1+zG+z^2*G(tz-z+G).

cp's OEIS Frontend

A115718 Inverse of number triangle A115717; a divide-and-conquer related triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A115716 A divide-and-conquer sequence.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A114583 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n and having k UHD's, where U=(1,1),H=(1,0),D=(1,-1) (0<=k<=floor(n/3)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula