A099376 -id:A099376 - cp's OEIS frontend

A120730 Another version of Catalan triangle A009766.

1, 0, 1, 0, 1, 1, 0, 0, 2, 1, 0, 0, 2, 3, 1, 0, 0, 0, 5, 4, 1, 0, 0, 0, 5, 9, 5, 1, 0, 0, 0, 0, 14, 14, 6, 1, 0, 0, 0, 0, 14, 28, 20, 7, 1, 0, 0, 0, 0, 0, 42, 48, 27, 8, 1, 0, 0, 0, 0, 0, 42, 90, 75, 35, 9, 1, 0, 0, 0, 0, 0, 0, 132, 165, 110, 44, 10, 1

Offset: 0

Philippe Deléham, Aug 17 2006, corrected Sep 15 2006

Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 1, -1, 0, 0, 1, -1, 0, 0, 1, -1, 0, 0, ...] DELTA [1, 0, 0, -1, 1, 0, 0, -1, 1, 0, 0, -1, 1, ...] where DELTA is the operator defined in A084938.
Aerated version gives A165408. - Philippe Deléham, Sep 22 2009
T(n,k) is the number of length n left factors of Dyck paths having k up steps. Example: T(5,4)=4 because we have UDUUU, UUDUU, UUUDU, and UUUUD, where U=(1,1) and D=(1,-1). - Emeric Deutsch, Jun 19 2011
With zeros omitted: 1,1,1,1,2,1,2,3,1,5,4,1,... = A008313. - Philippe Deléham, Nov 02 2011

			As a triangle, this begins:
  1;
  0,  1;
  0,  1,  1;
  0,  0,  2,  1;
  0,  0,  2,  3,  1;
  0,  0,  0,  5,  4,  1;
  0,  0,  0,  5,  9,  5,  1;
  0,  0,  0,  0, 14, 14,  6,  1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Cf. A000007, A000096, A000108, A001405, A001477, A003161, A005586, A005587.
Cf. A008313, A009766, A039598, A039599, A084938, A099376, A105523, A121725.
Cf. A126087, A128386, A121724, A128387, A129123, A132373, A132374, A132375.
Cf. A132889, A151162, A151254, A151281, A156195, A156361, A156362, A156566.
Cf. A156577, A165408, A357654.

A120730:= func< n,k | n gt 2*k select 0 else Binomial(n, k)*(2*k-n+1)/(k+1) >;
[A120730(n,k): k in [0..n], n in [0..13]]; // G. C. Greubel, Nov 07 2022

G := 4*z/((2*z-1+sqrt(1-4*z^2*t))*(1+sqrt(1-4*z^2*t))): Gser := simplify(series(G, z = 0, 13)): 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, k), k = 0 .. n) end do; # yields sequence in triangular form  # Emeric Deutsch, Jun 19 2011
# second Maple program:
b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, add(b(x-1, y+j), j=[-1, 1])))
    end:
T:= (n, k)-> b(n, 2*k-n):
seq(seq(T(n, k), k=0..n), n=0..14);  # Alois P. Heinz, Oct 13 2022

b[x_, y_]:= b[x, y]= If[y<0 || y>x, 0, If[x==0, 1, Sum[b[x-1, y+j], {j, {-1, 1}}] ]];
T[n_, k_] := b[n, 2 k - n];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Oct 21 2022, after Alois P. Heinz *)
T[n_, k_]:= If[n>2*k, 0, Binomial[n, k]*(2*k-n+1)/(k+1)];
Table[T[n, k], {n,0,13}, {k,0,n}]//Flatten (* G. C. Greubel, Nov 07 2022 *)

def A120730(n,k): return 0 if (n>2*k) else binomial(n, k)*(2*k-n+1)/(k+1)
flatten([[A120730(n,k) for k in range(n+1)] for n in range(14)]) # G. C. Greubel, Nov 07 2022

G.f.: G(t,z) = 4*z/((2*z-1+sqrt(1-4*t*z^2))*(1+sqrt(1-4*t*z^2))). - Emeric Deutsch, Jun 19 2011
Sum_{k=0..n} x^k*T(n,n-k) = A001405(n), A126087(n), A128386(n), A121724(n), A128387(n), A132373(n), A132374(n), A132375(n), A121725(n) for x=1,2,3,4,5,6,7,8,9 respectively. [corrected by Philippe Deléham, Oct 16 2008]
T(2*n,n) = A000108(n); A000108: Catalan numbers.
From Philippe Deléham, Oct 18 2008: (Start)
Sum_{k=0..n} T(n,k)^2 = A000108(n) and Sum_{n>=k} T(n,k) = A000108(k+1).
Sum_{k=0..n} T(n,k)^3 = A003161(n).
Sum_{k=0..n} T(n,k)^4 = A129123(n). (End)
Sum_{k=0..n}, T(n,k)*x^k = A000007(n), A001405(n), A151281(n), A151162(n), A151254(n), A156195(n), A156361(n), A156362(n), A156566(n), A156577(n) for x=0,1,2,3,4,5,6,7,8,9 respectively. - Philippe Deléham, Feb 10 2009
From G. C. Greubel, Nov 07 2022: (Start)
T(n, k) = 0 if n > 2*k, otherwise binomial(n, k)*(2*k-n+1)/(k+1).
Sum_{k=0..n} (-1)^k*T(n,k) = A105523(n).
Sum_{k=0..n} (-1)^k*T(n,k)^2 = -A132889(n), n >= 1.
Sum_{k=0..floor(n/2)} T(n-k, k) = A357654(n).
T(n, n-1) = A001477(n).
T(n, n-2) = [n=2] + A000096(n-3), n >= 2.
T(n, n-3) = 2*[n<5] + A005586(n-5), n >= 3.
T(n, n-4) = 5*[n<7] - 2*[n=4] + A005587(n-7), n >= 4.
T(2*n+1, n+1) = A000108(n+1), n >= 0.
T(2*n-1, n+1) = A099376(n-1), n >= 1. (End)

A115143 a(n) = -4binomial(2n-5, n-4)/n for n > 0 and a(0) = 1.

Original entry on oeis.org

1, -4, 2, 0, -1, -4, -14, -48, -165, -572, -2002, -7072, -25194, -90440, -326876, -1188640, -4345965, -15967980, -58929450, -218349120, -811985790, -3029594040, -11338026180, -42550029600, -160094486370, -603784920024, -2282138106804, -8643460269248, -32798844771700

Offset: 0

Wolfdieter Lang, Jan 13 2006

Previous name: Fourth convolution of A115140.
a(n+4) := - convolution ( A000108(n+1) ), n=0,1,... - Tilman Neumann, Jan 05 2009
Self-convolution of A115141. - R. J. Mathar, Sep 26 2012

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

Cf. A115139 - A115142, A115144 - A115149, A099376, A000108.

[1,-4,2] cat [-4*Binomial(2*n-5,n-4)/n: n in [3..30]]; // G. C. Greubel, Feb 12 2019

A115143 := n -> `if`(n=0, 1, -4*binomial(2*n-5,n-4)/n):
seq(A115143(n), n=0..28); # Peter Luschny, Feb 27 2017
A115143List := proc(m) local A, P, n; A := [1,-4,2,0]; P := [-1,0];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-1]]);
A := [op(A), P[-1]] od; A end: A115143List(27); # Peter Luschny, Mar 26 2022

Join[{1},Table[-4*Binomial[2n-5,n-4]/n,{n,30}]] (* Harvey P. Dale, Dec 01 2017 *)
CoefficientList[Series[(1-4*x+2*x^2+(1-2*x)*Sqrt[1-4*x])/2, {x,0,30}], x] (* G. C. Greubel, Feb 12 2019 *)

my(x='x+O('x^30)); Vec((1-4*x+2*x^2 +(1-2*x)*sqrt(1-4*x))/2) \\ G. C. Greubel, Feb 12 2019

[1,-4,2] + [-4*binomial(2*n-5,n-4)/n for n in (3..30)] # G. C. Greubel, Feb 12 2019

O.g.f.: 1/c(x)^4 = P(5, x) - x*P(4, x)*c(x) with the o.g.f. c(x) := (1-sqrt(1-4*x))/(2*x) of A000108 (Catalan numbers) and the polynomials P(n, x) defined in A115139. Here P(5, x) = 1-3*x+x^2 and P(4, x) = 1-2*x.
a(n) = -C4(n-4), n>=4, with C4(n) := A002057(n) (fourth convolution of Catalan numbers). a(0)=1, a(1)=-4, a(2)=2, a(3)=0. [1, -4, 2] is row n=4 of signed A034807 (signed Lucas polynomials). See A115149 and A034807 for comments.
E.g.f.: 1 - 3*x + 1/2*x^2 - x*Q(0), where Q(k)= 1 - 2*x/(k+2 - (k+2)*(2*k+1)/(2*k+1 - (k+2)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Apr 28 2013
D-finite with recurrence n*(n-4)*a(n) -2*(2*n-5)*(n-3)*a(n-1)=0. - R. J. Mathar, Sep 15 2024

Simpler name from Peter Luschny, Feb 27 2017

A355173 The Fuss-Catalan triangle of order 1, read by rows. Related to binary trees.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 3, 5, 0, 1, 4, 9, 14, 0, 1, 5, 14, 28, 42, 0, 1, 6, 20, 48, 90, 132, 0, 1, 7, 27, 75, 165, 297, 429, 0, 1, 8, 35, 110, 275, 572, 1001, 1430, 0, 1, 9, 44, 154, 429, 1001, 2002, 3432, 4862, 0, 1, 10, 54, 208, 637, 1638, 3640, 7072, 11934, 16796

Offset: 0

Peter Luschny, Jun 25 2022

The Fuss-Catalan triangle of order m is a regular, (0, 0)-based table recursively defined as follows: Set row(0) = [1] and row(1) = [0, 1]. Now assume row(n-1) already constructed and duplicate the last element of row(n-1). Next apply the cumulative sum m times to this list to get row(n). Here m = 1. (See the Python program for a reference implementation.)

This definition also includes the classical Fuss-Catalan numbers, since T(n, n) = A000108(n), or row 2 in A355262. For m = 2 see A355172 and for m = 3 A355174. More generally, for n >= 1 all Fuss-Catalan sequences (A355262(n, k), k >= 0) are the main diagonals of the Fuss-Catalan triangles of order n - 1.

			Table T(n, k) begins:
  [0] [1]
  [1] [0, 1]
  [2] [0, 1, 2]
  [3] [0, 1, 3,  5]
  [4] [0, 1, 4,  9,  14]
  [5] [0, 1, 5, 14,  28,  42]
  [6] [0, 1, 6, 20,  48,  90,  132]
  [7] [0, 1, 7, 27,  75, 165,  297, 429]
  [8] [0, 1, 8, 35, 110, 275,  572, 1001, 1430]
  [9] [0, 1, 9, 44, 154, 429, 1001, 2002, 3432, 4862]
Seen as an array reading the diagonals starting from the main diagonal:
  [0] 1, 1, 2,  5,  14,   42,  132,   429,  1430,   4862,   16796, ...  A000108
  [1] 0, 1, 3,  9,  28,   90,  297,  1001,  3432,  11934,   41990, ...  A000245
  [2] 0, 1, 4, 14,  48,  165,  572,  2002,  7072,  25194,   90440, ...  A099376
  [3] 0, 1, 5, 20,  75,  275, 1001,  3640, 13260,  48450,  177650, ...  A115144
  [4] 0, 1, 6, 27, 110,  429, 1638,  6188, 23256,  87210,  326876, ...  A115145
  [5] 0, 1, 7, 35, 154,  637, 2548,  9996, 38760, 149226,  572033, ...  A000588
  [6] 0, 1, 8, 44, 208,  910, 3808, 15504, 62016, 245157,  961400, ...  A115147
  [7] 0, 1, 9, 54, 273, 1260, 5508, 23256, 95931, 389367, 1562275, ...  A115148

A000108 (main diagonal), A000245 (subdiagonal), A002057 (diagonal 2), A000344 (diagonal 3), A000027 (column 2), A000096 (column 3), A071724 (row sums), A000958 (alternating row sums), A262394 (main diagonal of array).
Variants: A009766 (main variant), A030237, A130020.
Cf. A123110 (triangle of order 0), A355172 (triangle of order 2), A355174 (triangle of order 3), A355262 (Fuss-Catalan array).
Cf. A115144, A115145, A000588, A115147, A115148.

from functools import cache
from itertools import accumulate
@cache
def Trow(n: int) -> list[int]:
    if n == 0: return [1]
    if n == 1: return [0, 1]
    row = Trow(n - 1) + [Trow(n - 1)[n - 1]]
    return list(accumulate(row))
for n in range(11): print(Trow(n))

The general formula for the Fuss-Catalan triangles is, for m >= 0 and 0 <= k <= n:
FCT(n, k, m) = (m*(n - k) + m + 1)*(m*n + k - 1)!/((m*n + 1)!*(k - 1)!) for k > 0 and FCT(n, 0, m) = 0^n. The case considered here is T(n, k) = FCT(n, k, 1).
T(n, k) = (n - k + 2)*(n + k - 1)!/((n + 1)!*(k - 1)!) for k > 0; T(n, 0) = 0^n.
The g.f. of row n of the FC-triangle of order m is 0^n + (x - (m + 1)*x^2) / (1 - x)^(m*n + 2), thus:
T(n, k) = [x^k] (0^n + (x - 2*x^2)/(1 - x)^(n + 2)).

A368378 Arises from enumeration of a certain class of partial zig-zag knight's paths on the square grid.

Original entry on oeis.org

0, 1, 1, 2, 4, 5, 14, 14, 48, 42, 165, 132, 572, 429, 2002, 1430, 7072, 4862, 25194, 16796, 90440, 58786, 326876, 208012, 1188640, 742900, 4345965, 2674440, 15967980, 9694845, 58929450, 35357670, 218349120, 129644790, 811985790, 477638700, 3029594040

Offset: 0

N. J. A. Sloane, Feb 18 2024

nonn

It would be nice to have a more precise definition.

Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022). Also arXiv:2206.12087 [math.CO], Jan 2023. See Section 3.2.

Cf. A368379, A368380.

The two bisections are A000108 and A099376. The first differences are A026008.

r = (1 - 2z^2 - Sqrt[1-4z^2]) / (2z^2);
gf = (r^2 z + r u^2 + r u + 2 r z + z) / (z (1 - r u));
Table[SeriesCoefficient[gf,{u,0,1},{z,0,n}], {n,0,50}] (* Andrei Zabolotskii, Jul 25 2025 *)

G.f.: (1/x + 1 + 2*R(x) + R(x)^2) * R(x), where R(x) = (1 - sqrt(1-4*x^2)) / (2*x^2) - 1. - Andrei Zabolotskii, Jul 25 2025

Terms a(11) and beyond from Andrei Zabolotskii, Jul 25 2025

cp's OEIS Frontend

A120730 Another version of Catalan triangle A009766.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A115143 a(n) = -4*binomial(2*n-5, n-4)/n for n > 0 and a(0) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A355173 The Fuss-Catalan triangle of order 1, read by rows. Related to binary trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

A368378 Arises from enumeration of a certain class of partial zig-zag knight's paths on the square grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A115143 a(n) = -4binomial(2n-5, n-4)/n for n > 0 and a(0) = 1.