A005807 -id:A005807 - cp's OEIS frontend

A274257 Number of factor-free Dyck words with slope 4/3 and length 7n.

1, 5, 52, 880, 17856, 399296, 9491008, 235274240, 6014201600, 157387037696, 4195621863424, 113534211297280, 3110485641494528, 86107512380129280, 2404899661362184192, 67680890349732102144, 1917436905101367443456, 54640222663002565640192, 1565130555077611323392000, 45039415225401829826232320

Offset: 0

Michael D. Weiner, Jun 16 2016

nonn

a(n) is the number of lattice paths (allowing only north and east steps) starting at (0,0) and ending at (3n,4n) that stay below the line y=4/3x and also do not contain a proper subpath of smaller size.

			a(2) = 52 since there are 52 lattice paths (allowing only north and east steps) starting at (0,0) and ending at (6,8) that stay below the line y=4/3x and also do not contain a proper subpath of small size; e.g., EENEENENNENNNN is a factor-free Dyck word but ENEEENNENNENNN contains the factor EENNENN.

Daniel Birmajer, Juan B. Gil and Michael D. Weiner, On rational Dyck paths and the enumeration of factor-free Dyck words, arXiv:1606.02183 [math.CO], 2016.
Daniel Birmajer, Juan B. Gil and Michael D. Weiner, On rational Dyck paths and the enumeration of factor-free Dyck words, Discrete Applied Mathematics, 244 (2018), 36-43.
P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Mathematics, 225 (2000), 121-135.

Cf. A005807 (slope 3/2), A274052 (slope 5/2), A274244 (slope 7/2), A274256 (slope 9/2), A274258 (slope 5/3), A274259 (slope 7/3).

m = 20; f[_] = 0;
Do[f[x_] = (1/(x+1)^4)(-(x^2 (x+1) f[x]^4) + x f[x]^6 + (x-1) x f[x]^5 - (x - 3) x (x+1)^2 f[x]^3 + x (x+1)^3 f[x]^2 + (x+1)^5) + O[x]^m, {m}];
CoefficientList[f[x], x] (* Jean-François Alcover, Sep 28 2019 *)

G.f. satisfies: 0 = x*f^6 + x*(x-1)*f^5 - x^2*(x+1)*f^4 - x*(x-3)*(x+1)^2*f^3 + x*(x+1)^3*f^2 - (x+1)^4*f + (x+1)^5. - Michael D. Weiner, Jan 14 2019

Conjectural o.g.f.: Let E(x) = exp( Sum_{n >= 1} binomial(7*n, 3*n)*x^n/n ). Then A(x) = ( x/series reversion of x*E(x) )^(1/7) = 1 + 5*x + 52*x^2 + 880*x^3 + .... Equivalently, [x^n]( A(x)^(7*n) ) = binomial(7*n, 3*n) for n = 0,1,2,.... - Peter Bala, Jan 01 2020

A274259 Number of factor-free Dyck words with slope 7/3 and length 10n.

Original entry on oeis.org

1, 12, 570, 44689, 4223479, 441010458, 49014411306, 5685822210429, 680500195656621, 83406972284096638, 10416465145620729162, 1320749077779826216029, 169570747575202480367168, 22000830732097549119672094, 2880094468241888675318895339, 379941591968957300338548388051, 50458777676743899501139029335858

Offset: 0

Michael D. Weiner, Jun 16 2016

nonn

a(n) is the number of lattice paths (allowing only north and east steps) starting at (0,0) and ending at (3n,7n) that stay below the line y=7/3x and also do not contain a proper subpath of smaller size.

			a(2) = 570 since there are 570 lattice paths (allowing only north and east steps) starting at (0,0) and ending at (6,14) that stay below the line y=7/3x and also do not contain a proper subpath of small size; e.g., ENNENENNNENNENNNENNN is a factor-free Dyck word but ENNENNENNEENNNNNENNN contains the factor ENNEENNNNN.

Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On rational Dyck paths and the enumeration of factor-free Dyck words, arXiv:1606.02183 [math.CO], 2016.
P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Mathematics, 225 (2000), 121-135.

Factor-free Dyck words: A005807 (slope 3/2), A274052 (slope 5/2), A274244 (slope 7/2), A274256 (slope 9/2), A274257 (slope 4/3), A274258 (slope 5/3).

Conjectural o.g.f.: Let E(x) = exp( Sum_{n >= 1} binomial(10*n, 3*n)*x^n/n ). Then A(x) = ( x/series reversion of x*E(x) )^(1/10) = 1 + 12*x + 570*x^2 + 44689*x^3 + ... . Equivalently, [x^n]( A(x)^(10*n) ) = binomial(10*n, 3*n) for n = 0,1,2,... . - Peter Bala, Jan 03 2020

A106534 Sum array of Catalan numbers (A000108) read by upward antidiagonals.

Original entry on oeis.org

1, 2, 1, 5, 3, 2, 15, 10, 7, 5, 51, 36, 26, 19, 14, 188, 137, 101, 75, 56, 42, 731, 543, 406, 305, 230, 174, 132, 2950, 2219, 1676, 1270, 965, 735, 561, 429, 12235, 9285, 7066, 5390, 4120, 3155, 2420, 1859, 1430, 51822, 39587, 30302, 23236, 17846, 13726, 10571, 8151, 6292, 4862

Offset: 0

Philippe Deléham, May 30 2005

The underlying array A is A(n, k) = Sum_{j=0..n} binomial(n, j)*A000108(k+j), n >= 0, k>= 0. See the example section. - Wolfdieter Lang, Oct 04 2019

			From _Wolfdieter Lang_, Oct 04 2019: (Start)
The triangle T(n, k) begins:
n\k      0      1      2      3     4     5     6     7     8     9    10 ...
0:       1
1:       2      1
2:       5      3      2
3:      15     10      7      5
4:      51     36     26     19    14
5:     188    137    101     75    56    42
6:     731    543    406    305   230   174   132
7:    2950   2219   1676   1270   965   735   561   429
8:   12235   9285   7066   5390  4120  3155  2420  1859  1430
9:   51822  39587  30302  23236 17846 13726 10571  8151  6292  4862
10: 223191 171369 131782 101480 78244 60398 46672 36101 27950 21658 16796
... reformatted and extended.
-------------------------------------------------------------------------
The array A(n, k) begins:
n\k  0   1    2    3     4     5      6 ...
-------------------------------------------
0:   1   1    2    5    14    42    132 ... A000108
1    2   3    7   19    56   174    561 ... A005807
2:   5  10   26   75   230   735   2420 ...
3:  15  36  101  305   965  3155  10571 ...
4:  51 137  406 1270  4120 13726  46672 ...
5: 188 543 1676 5390 17846 60398 207963 ...
... (End)

G. C. Greubel, Rows n = 0..50 of the triangle, flattened
Paul Barry and A. Hennessy, The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010) # 10.8.2, page 5.

Columns: A007317, A002212, see also A045868, A055452-A055455.
Diagonals: A000108, A005807.
Cf. A059346 (Catalan difference array as triangle).

function T(n,k)
  if k gt n then return 0;
  elif k eq n then return Catalan(n);
  else return T(n-1, k) + T(n, k+1);
  end if; return T;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Aug 18 2021

# Uses floating point, precision might have to be adjusted.
C := n -> binomial(2*n,n)/(n+1);
H := (n,k) -> hypergeom([k-n,k+1/2],[k+2],-4);
T := (n,k) -> C(k)*H(n,k);
seq(print(seq(round(evalf(T(n,k),32)),k=0..n)),n=0..7);
# Peter Luschny, Aug 16 2012

T[n_, n_] := CatalanNumber[n]; T[n_, k_] /; 0 <= k < n := T[n-1, k] + T[n, k+1]; T[, ] = 0; Table[T[n, k], {n, 0, 9}, {k, 0, n}] (* Jean-François Alcover, Jun 11 2019 *)

def T(n, k) :
    if k > n : return 0
    if n == k : return binomial(2*n, n)/(n+1)
    return T(n-1, k) + T(n, k+1)
A106534 = lambda n,k: T(n, k)
for n in (0..5): [A106534(n,k) for k in (0..n)] # Peter Luschny, Aug 16 2012

T(n, k) = 0 if k > n; T(n, n) = A000108(n); T(n, k) = T(n-1, k) + T(n, k+1) if 0 <= k < n.
T(n, k) = binomial(2*k,k)/(k+1)*hypergeometric([k-n, k+1/2], [k+2], -4). - Peter Luschny, Aug 16 2012
T(n, k) = A(n-k, k) = Sum_{j=0..n-k} binomial(n-k, j)*A000108(k+j), n >= 0, k = 0..n. - Wolfdieter Lang, Oct 03 2019
G.f.: (sqrt(1-4*x*y)-sqrt((5*x-1)/(x-1)))/(2*x*(x*y-y+1)). - Vladimir Kruchinin, Jan 12 2024

A274258 Number of factor-free Dyck words with slope 5/3 and length 8n.

Original entry on oeis.org

1, 7, 133, 4140, 154938, 6398717, 281086555, 12882897819, 609038885805, 29481041746958, 1453894927584477, 72789271870852237, 3689808842747726368, 189006099916444293090, 9768094831949586349262, 508712466332195692590121, 26670630123516854616641671, 1406503552584980596900001922, 74559627811441047591493767590

Offset: 0

Michael D. Weiner, Jun 16 2016

nonn

a(n) is the number of lattice paths (allowing only north and east steps) starting at (0,0) and ending at (3n,5n) that stay below the line y=5/3x and also do not contain a proper subpath of smaller size.

			a(2) = 133 since there are 133 lattice paths (allowing only north and east steps) starting at (0,0) and ending at (6,10) that stay below the line y=5/3x and also do not contain a proper subpath of small size; e.g., ENEEEENNNNENNNNN is a factor-free Dyck word but ENEENNENNNEENNNN contains the factor EENNENNN.

Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On rational Dyck paths and the enumeration of factor-free Dyck words, arXiv:1606.02183 [math.CO], 2016.
P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Mathematics, 225 (2000), 121-135.

Factor-free Dyck words: A005807 (slope 3/2), A274052 (slope 5/2), A274244 (slope 7/2), A274256 (slope 9/2), A274257 (slope 4/3), A274259 (slope 7/3).

Conjectural o.g.f.: Let E(x) = exp( Sum_{n >= 1} binomial(8*n, 3*n)*x^n/n ). Then A(x) = ( x/series reversion of x*E(x) )^(1/8) = 1 + 7*x + 133*x^2 + 4140*x^3 + ... . Equivalently, [x^n]( A(x)^(8*n) ) = binomial(8*n, 3*n) for n = 0,1,2,... . - Peter Bala, Jan 01 2020

A000778 a(n) = Catalan(n) + Catalan(n+1) - 1.

Original entry on oeis.org

1, 2, 6, 18, 55, 173, 560, 1858, 6291, 21657, 75581, 266797, 950911, 3417339, 12369284, 45052514, 165002459, 607283489, 2244901889, 8331383609, 31030387439, 115948830659, 434542177289, 1632963760973, 6151850548775, 23229299473603, 87900903988155

Offset: 0

N. J. A. Sloane

nonn

T. D. Noe, Table of n, a(n) for n = 0..200
J. R. Stembridge, Some combinatorial aspects of reduced words in finite Coxeter groups, Trans. Amer. Math. Soc. 349 (1997), no. 4, 1285-1332.

Cf. A000108.

Equals A005807(n) - 1. Cf. A071716.

Table[CatalanNumber[n] + CatalanNumber[n + 1] - 1, {n, 0, 200}] (* T. D. Noe, Jun 20 2012 *)

D-finite with recurrence (n+2)*a(n) +(-5*n-4)*a(n-1) +(3*n+4)*a(n-2) +(5*n-16)*a(n-3) +2*(-2*n+7)*a(n-4)=0. - R. J. Mathar, Jun 17 2020

A067294 Third column of triangle A028364.

Original entry on oeis.org

5, 9, 23, 66, 202, 645, 2123, 7150, 24518, 85306, 300390, 1068484, 3833364, 13855085, 50401395, 184392150, 677998830, 2504191470, 9286661010, 34564913820, 129077071500, 483474711330, 1815928888254

Offset: 0

Wolfdieter Lang, Feb 05 2002

The first two columns give: A000108 (Catalan) and A005807. The next two columns give: A067295-6.

First differences are in A071747.

a(n)= A028364(n+2, 2) = C(0)*C(n+2)+C(1)*C(n+1)+C(2)*C(n), with the Catalan numbers C(n)=A000108(n). a(n)= ((11*n^2+28*n+15)/(2*(2*n+1)*(2*n+3)))*C(n+2).

G.f.: (c2(x)*c(x)-(c2(x)-1)/x)/x^2, with c2(x) := 1+x+2*x^2 and c(x) G.f. for Catalan numbers A000108.

A133603 The matrix-vector product A133566 * A000108.

Original entry on oeis.org

1, 1, 3, 5, 19, 42, 174, 429, 1859, 4862, 21658, 58786, 266798, 742900, 3417340, 9694845, 45052515, 129644790, 607283490, 1767263190, 8331383610, 24466267020, 115948830660, 343059613650, 1632963760974, 4861946401452

Offset: 0

Gary W. Adamson, Sep 18 2007

A133602 is a companion sequence.

			a(5) = C(5) = 42.
a(6) = 174 = C(6) + C(5) = 132 + 42.

Cf. A133566, A000108, A133602, A024492 (bisection).

A133603 := proc(n)
    add(A133566(n+1,k+1)*A000108(k),k=0..n) ;
end proc: # R. J. Mathar, Jun 20 2015

A133566 * A000108 where A133566 = an infinite lower triangular matrix and A000108 = the Catalan sequence. For odd n, a(n) = C(n). For even n, a(n) = C(n) + C(n-1) = A005807(n-1).
Conjecture: n*(n-2)*(3*n-1)*(n+1)*a(n) -8*n*(2*n-3)*a(n-1) -4*(n-1)*(3*n+2)*(
2*n-3)*(2*n-5)*a(n-2)=0. - R. J. Mathar, Jun 20 2015

A350584 Triangle read by rows, T(n, k) = [x^k] ((2x^3 - 3x^2 - x + 1)/(1 - x)^(n + 2)), for n >= 1 and 0 <= k < n.

Original entry on oeis.org

1, 1, 3, 1, 4, 7, 1, 5, 12, 19, 1, 6, 18, 37, 56, 1, 7, 25, 62, 118, 174, 1, 8, 33, 95, 213, 387, 561, 1, 9, 42, 137, 350, 737, 1298, 1859, 1, 10, 52, 189, 539, 1276, 2574, 4433, 6292, 1, 11, 63, 252, 791, 2067, 4641, 9074, 15366, 21658

Offset: 1

Peter Luschny, Mar 27 2022

			Triangle starts:
[1] [1]
[2] [1,  3]
[3] [1,  4,  7]
[4] [1,  5, 12,  19]
[5] [1,  6, 18,  37,  56]
[6] [1,  7, 25,  62, 118,  174]
[7] [1,  8, 33,  95, 213,  387,  561]
[8] [1,  9, 42, 137, 350,  737, 1298, 1859]
[9] [1, 10, 52, 189, 539, 1276, 2574, 4433, 6292]

A280891 (row sums), A135339 (alternating row sums), A005807 or A071716 (main diagonal).

# Compare the analogue algorithm for the Bell triangle in A046937.
A350584Triangle := proc(len) local A, P, T, n; A := [2]; P := [1]; T := [[1]];
for n from 1 to len-1 do P := ListTools:-PartialSums([op(P), A[-1]]);
A := P; T := [op(T), P] od; T end:
A350584Triangle(10): ListTools:-Flatten(%);
# Alternative:
ogf := n -> (2*x^3 - 3*x^2 - x + 1)/(1 - x)^(n + 2):
ser := n -> series(ogf(n), x, n):
row := n -> seq(coeff(ser(n), x, k), k = 0..n-1):
seq(row(n), n = 1..10);

A133602 The matrix-vector product A133080 * A000108.

Original entry on oeis.org

1, 2, 2, 7, 14, 56, 132, 561, 1430, 6292, 16796, 75582, 208012, 950912, 2674440, 12369285, 35357670, 165002460, 477638700, 2244901890, 6564120420, 31030387440, 91482563640, 434542177290, 1289904147324, 6151850548776

Offset: 0

Gary W. Adamson, Sep 18 2007

A133603 is a companion sequence.

			a(4) = C(4) = 14.
a(5) = 56 = C(5) + C(4) = 42 + 14.

Cf. A097806, A133080, A000108, A133603.

from sympy import catalan
def a005807(n): return catalan(n) + catalan(n + 1)
def a048990(n): return catalan(2*n)
l=[1, 2]
for n in range(2, 31): l+=[a048990(n//2) if n%2==0 else a005807(n - 1)]
print(l) # Indranil Ghosh, Jul 15 2017

A133080 * A000108, where A133080 = an infinite lower triangular matrix and A000108 = the Catalan sequence as a vector.
a(2n) = A048990(n).
a(2n+1) = A005807(2n).
Conjecture: n*(n-1)*(n-3)*(3*n-4)*a(n) -8*(n-1)*(2*n-5)*a(n-1) -4*(n-2)*(3*n-1)*(2*n-5)*(2*n-7)*a(n-2)=0. - R. J. Mathar, Jun 20 2015

A323212 The Fibonacci-Catalan Hybrid. Expansion of 1 + x(2(x + 1))/(sqrt(1 - 4y) - 2x*(x + 1) + 1). Square array read by descending antidiagonals, A(n,k) for n,k >= 0.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 2, 3, 3, 0, 5, 7, 7, 5, 0, 14, 19, 19, 15, 8, 0, 42, 56, 56, 46, 30, 13, 0, 132, 174, 174, 146, 103, 58, 21, 0, 429, 561, 561, 477, 351, 220, 109, 34, 0, 1430, 1859, 1859, 1595, 1205, 801, 453, 201, 55, 0, 4862, 6292, 6292, 5434, 4180, 2884, 1756, 908, 365, 89

Offset: 0

Peter Luschny, Feb 14 2019

			      1,   0,    0,    0,     0,      0,      0,       0,       0, ...
      1,   1,    2,    5,    14,     42,    132,     429,    1430, ... [A000108]
      2,   3,    7,   19,    56,    174,    561,    1859,    6292, ... [A005807]
      3,   7,   19,   56,   174,    561,   1859,    6292,   21658, ... [A005807]
      5,  15,   46,  146,   477,   1595,   5434,   18798,   65858, ...
      8,  30,  103,  351,  1205,   4180,  14651,   51844,  185028, ...
     13,  58,  220,  801,  2884,  10372,  37401,  135420,  492558, ...
     21, 109,  453, 1756,  6621,  24674,  91532,  339184, 1257762, ...
     34, 201,  908, 3734, 14719,  56796, 216698,  821848, 3107583, ...
     55, 365, 1781, 7746, 31872, 127245, 499164, 1937439, 7470819, ...
A000045,A023610,...
Seen as a triangle a refinement of A000958:
[0]                                1
[1]                              0, 1
[2]                            0, 1, 2
[3]                           0, 2, 3, 3
[4]                         0, 5, 7, 7, 5
[5]                      0, 14, 19, 19, 15, 8
[6]                   0, 42, 56, 56, 46, 30, 13
[7]               0, 132, 174, 174, 146, 103, 58, 21
[8]            0, 429, 561, 561, 477, 351, 220, 109, 34
[9]       0, 1430, 1859, 1859, 1595, 1205, 801, 453, 201, 55

Antidiagonal sums (or row sums of the triangle) are A000958.

Cf. A000045, A000108, A023610, A005807.

gf := 1 + x*(2*(x + 1))/(sqrt(1 - 4*y) - 2*x*(x + 1) + 1):
serx := series(gf, x, 20): sery := n -> series(coeff(serx, x, n), y, 20):
row := n -> seq(coeff(sery(n), y, j), j=0..9):
seq(lprint(row(n)), n=0..9);

m = 11; T = PadRight[CoefficientList[#+O[y]^m, y], m]& /@ CoefficientList[1 + 2x(x+1)/(Sqrt[1-4y] - 2x(x+1) + 1) + O[x]^m, x]; Table[T[[n-k+1, k]], {n, 1, m}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Mar 20 2019 *)

cp's OEIS Frontend

A274257 Number of factor-free Dyck words with slope 4/3 and length 7n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A274259 Number of factor-free Dyck words with slope 7/3 and length 10n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A106534 Sum array of Catalan numbers (A000108) read by upward antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

A274258 Number of factor-free Dyck words with slope 5/3 and length 8n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A000778 a(n) = Catalan(n) + Catalan(n+1) - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A067294 Third column of triangle A028364.

Views

Author

Keywords

Comments

Crossrefs

Formula

A133603 The matrix-vector product A133566 * A000108.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A350584 Triangle read by rows, T(n, k) = [x^k] ((2*x^3 - 3*x^2 - x + 1)/(1 - x)^(n + 2)), for n >= 1 and 0 <= k < n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

A133602 The matrix-vector product A133080 * A000108.

Views

A350584 Triangle read by rows, T(n, k) = [x^k] ((2x^3 - 3x^2 - x + 1)/(1 - x)^(n + 2)), for n >= 1 and 0 <= k < n.

A323212 The Fibonacci-Catalan Hybrid. Expansion of 1 + x(2(x + 1))/(sqrt(1 - 4y) - 2x*(x + 1) + 1). Square array read by descending antidiagonals, A(n,k) for n,k >= 0.