A371965 -id:A371965 - cp's OEIS frontend

A371963 a(n) is the sum of all valleys in the set of Catalan words of length n.

0, 0, 0, 0, 1, 8, 44, 209, 924, 3927, 16303, 66691, 270181, 1087371, 4356131, 17394026, 69289961, 275543036, 1094352236, 4342295396, 17218070066, 68239187876, 270351828476, 1070824260326, 4240695090452, 16792454677874, 66492351226050, 263285419856250, 1042540731845950

Offset: 0

Stefano Spezia, Apr 14 2024

nonn

			a(4) = 1 because there is 1 Catalan word of length 4 with one valley: 0101.
a(5) = 8 because there are 8 Catalan words of length 5 with one valley: 00101, 01010, 01011, 01012, 01101, 01201, and 01212 (see Figure 9 at p. 14 in Baril et al.).

Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, Enumerating runs, valleys, and peaks in Catalan words, arXiv:2404.05672 [math.CO], 2024. See Corollary 4.5, p. 15.

Cf. A371964, A371965.

Cf. A003516.

a:= proc(n) option remember; `if`(n<4, 0,
      a(n-1)+binomial(2*n-3, n-4))
    end:
seq(a(n), n=0..28);  # Alois P. Heinz, Apr 15 2024

CoefficientList[Series[(1 - 5x+5x^2-(1-3x+x^2)Sqrt[1-4x])/(2(1-x)x Sqrt[1-4x]),{x,0,28}],x]

from math import comb
def A371963(n): return sum(comb((n-i<<1)-3,n-i-4) for i in range(n-3)) # Chai Wah Wu, Apr 15 2024

G.f.: (1-5*x+5*x^2-(1-3*x+x^2)*sqrt(1-4*x))/(2*(1-x)*x*sqrt(1-4*x)).
a(n) = Sum_{i=1..n-1} binomial(2*(n-i)-1,n-i-3).
a(n) ~ 2^(2*n)/(6*sqrt(Pi*n)).
a(n) - a(n-1) = A003516(n-2).

A371964 a(n) is the sum of all symmetric valleys in the set of Catalan words of length n.

Original entry on oeis.org

0, 0, 0, 0, 1, 7, 35, 155, 650, 2652, 10660, 42484, 168454, 665874, 2627130, 10353290, 40775045, 160534895, 631970495, 2487938015, 9795810125, 38576953505, 151957215305, 598732526105, 2359771876175, 9303298456451, 36688955738099, 144732209103699, 571117191135799

Offset: 0

Stefano Spezia, Apr 14 2024

nonn

			a(4) = 1 because there is 1 Catalan word of length 4 with one symmetric valley: 0101.
a(5) = 7 because there are 7 Catalan words of length 5 with one symmetric valley: 00101, 01001, 01010, 01011, 01012, 01101, and 01212 (see example at p. 16 in Baril et al.).

Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, Enumerating runs, valleys, and peaks in Catalan words, arXiv:2404.05672 [math.CO], 2024. See Corollary 4.7, pp. 16-17.

Cf. A371963, A371965.

Cf. A000108, A002694, A079309.

a:= proc(n) option remember; `if`(n<4, 0,
      a(n-1)+binomial(2*n-4, n-4))
    end:
seq(a(n), n=0..28);  # Alois P. Heinz, Apr 15 2024

CoefficientList[Series[(1-4x+2x^2-(1-2x)Sqrt[1-4x])/(2(1-x) Sqrt[1-4x]),{x,0,29}],x]

from math import comb
def A371964(n): return sum(comb((n-i<<1)-4,n-i-4) for i in range(n-3)) # Chai Wah Wu, Apr 15 2024

G.f.: (1 - 4*x + 2*x^2 - (1 - 2*x)*sqrt(1 - 4*x))/(2*(1 - x)*sqrt(1 - 4*x)).
a(n) = (3*n - 2)*A000108(n-1) - A079309(n) for n > 0.
a(n) ~ 2^(2*n)/(12*sqrt(Pi*n)).
a(n)/A371963(n) ~ 1/2.
a(n) - a(n-1) = A002694(n-2).

A275289 Number of set partitions of [n] with symmetric block size list of length three.

Original entry on oeis.org

1, 2, 7, 19, 56, 160, 463, 1337, 3874, 11241, 32682, 95172, 277577, 810706, 2370839, 6941473, 20345618, 59692831, 175295996, 515217034, 1515478535, 4460940067, 13140081770, 38729776774, 114221851951, 337050020750, 995097461503, 2939337252651, 8686270661400

Offset: 3

Alois P. Heinz, Jul 22 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..1000
Wikipedia, Partition of a set

Column k=3 of A275281.

G.f.: -(1/2)*(3*x-1+sqrt((1-3*x)*(x+1)*(2*x-1)^2))/((3*x-1)*(x+1)).
a(n) ~ 3^(n-1/2) / (4*sqrt(Pi*n)). - Vaclav Kotesovec, Aug 02 2016
Recurrence: (n-3)*n*a(n) = (n^2 - 3*n + 4)*a(n-1) + (n-2)*(5*n - 11)*a(n-2) + 3*(n-3)*(n-2)*a(n-3). - Vaclav Kotesovec, Aug 02 2016
From Mélika Tebni, Jun 20 2025: (Start)
a(n) = Sum_{k=floor(n/2)..n-2} binomial(n-1, k+1)*binomial(k, n-(k+1)).
Inverse binomial transform of A371965. (End)

A372883 Irregular triangle read by rows: T(n,k) is the number of flattened Catalan words of length n with exactly k symmetric peaks, with k >= 0.

Original entry on oeis.org

1, 2, 4, 1, 9, 5, 23, 17, 1, 63, 51, 8, 176, 149, 39, 1, 491, 439, 153, 11, 1362, 1308, 540, 70, 1, 3762, 3912, 1812, 342, 14, 10369, 11671, 5935, 1439, 110, 1, 28559, 34637, 19175, 5541, 645, 17, 78653, 102222, 61302, 20214, 3170, 159, 1, 216638, 300190, 194080, 71242, 13903, 1089, 20

Offset: 1

Stefano Spezia, May 15 2024

			The irregular triangle begins:
     1;
     2;
     4,    1;
     9,    5;
    23,   17,    1;
    63,   51,    8;
   176,  149,   39,   1;
   491,  439,  153,  11;
  1362, 1308,  540,  70,  1;
  3762, 3912, 1812, 342, 14;
  ...
T(4,1) = 5 since there are 5 flattened Catalan words of length 4 with 1 symmetric peak: 0100, 0101, 0010, 0110, and 0121.

Jean-Luc Baril, Pamela E. Harris, and José L. Ramírez, Flattened Catalan Words, arXiv:2405.05357 [math.CO], 2024. See pp. 21-22.

Cf. A007051 (row sums), A290900 (2nd column), A369328 (1st column), A371965, A372879, A372884.

T[n_,k_]:=SeriesCoefficient[x(1-x)(1-2x)/(1-5x+8x^2-5x^3-x^2y+2x^3y),{x,0,n},{y,0,k}]; Table[T[n,k],{n,14},{k,0,Floor[(n-1)/2]}]//Flatten

G.f.: x*(1 - x)*(1 - 2*x)/(1 - 5*x + 8*x^2 - 5*x^3 - x^2*y + 2*x^3*y).

Sum_{k>=0} T(n,k) = A007051(n-1).

A377441 Square array T(n, k) read by rising antidiagonals. Row n has the ordinary generating function (-(nx^3-(n+1)x^2+x) + sqrt((nx^3-(n+1)x^2+x)^2 - 4(x^3-x^2)((n+1)x^2-x)))/(2(x^3-x^2)).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 2, 6, 14, 1, 1, 2, 7, 21, 42, 1, 1, 2, 8, 30, 78, 132, 1, 1, 2, 9, 41, 136, 299, 429, 1, 1, 2, 10, 54, 222, 630, 1172, 1430, 1, 1, 2, 11, 69, 342, 1221, 2959, 4677, 4862, 1, 1, 2, 12, 86, 502, 2192, 6774, 14058, 18947, 16796, 1, 1, 2, 13, 105, 708, 3687, 14129, 37853, 67472, 77746, 58786, 1, 1, 2, 14, 126, 966, 5874, 27184

Offset: 0

Thomas Scheuerle, Oct 28 2024

The Hankel sequence transform of row n satisfies the Somos-4 recurrence c(k) = (c(k-1) * c(k-3) + n*c(k-2)^2) / c(k-4). All Somos-4 sequences which are beginning with 1, 1, 1, 1, n, ... will be covered, but the Hankel transform will start with the terms 1, n, ... in each case.

			The array begins:
  [0] 1, 1, 2,  5, 14,  42,  132,   429,   1430, ... = A000108
  [1] 1, 1, 2,  6, 21,  78,  299,  1172,   4677, ... = A254316
  [2] 1, 1, 2,  7, 30, 136,  630,  2959,  14058, ...
  [3] 1, 1, 2,  8, 41, 222, 1221,  6774,  37853, ...
  [4] 1, 1, 2,  9, 54, 342, 2192, 14129,  91494, ...
  [5] 1, 1, 2, 10, 69, 502, 3687, 27184, 201045, ...

Cf. A377442 (extension for -n), A105633 (row -1), A152172 (row -2).
Cf. A000108 (row 0), A254316 (row 1).
Cf. A000012 (Hankel transform of row 0), A006720 (Hankel transform of row 1).
Cf. A330025 (Hankel transform of row -1), A328380 (Hankel transform of row -2).
Cf. A371965, A377443.

T(n, max_k) = Vec(-2*((n+1)*x-1)/((x-1)*(n*x-1)+((n*x^2-(n+1)*x+1)^2-4*x*(x-1)*((n+1)*x-1)+O(x^max_k))^(1/2)))

The generating function A(x) of row n satisfies: 0 = (x^3 - x^2)*A(x)^2 + (n*x^3 - (n+1)*x^2 - x)*A(x) + ((n+1)*x^2 - x).
Let d(m, n) = ( d(m-3, n)*d(m-2, n) + n)/( d(m-5, n)*d(m-4, n)*d(m-3, n)^2*d(m-2, n)^2*d(m-1, n) ) for m = even and d(m, n) = 1/( d(m-1, n)*d(m-2, n) ) for m = odd with d( < 1 , n) = 1, then the generating function of row n can be expanded as continued fractions: 1/(1 - x/(1 - d(0, n)*x/(1 - d(1, n)*x/(1 - d(2, n)*x/(...))))).
d(m, n)*d(m+1, n) is a rational solution in x of the elliptic equation y^2 = -4*x^3 + ((n+1)^2 + 8)*x^2 - 2*(n+3)*x + 1. The division polynomials for multiples of the point with x = 1, correspondent to the Hankel transform of row n in the array T(n, k).
T(n, k + 2) = Sum_{j >= 0} A377443(k, j)*n^j. This polynomial starts with A000108(k+2) + A371965(k+2)*n + ..., where A371965 is known to count peaks in the set of Catalan words of length k.

A372879 Irregular triangle read by rows: T(n,k) is the number of flattened Catalan words of length n with exactly k short peak, with k >= 0.

Original entry on oeis.org

1, 2, 4, 1, 9, 5, 22, 18, 1, 56, 58, 8, 145, 178, 41, 1, 378, 532, 173, 11, 988, 1563, 656, 73, 1, 2585, 4535, 2327, 381, 14, 6766, 13030, 7888, 1726, 114, 1, 17712, 37140, 25872, 7124, 709, 17, 46369, 105156, 82758, 27534, 3739, 164, 1, 121394, 296040, 259542, 101350, 17632, 1184, 20

Offset: 1

Stefano Spezia, May 15 2024

			The irregular triangle begins:
    1;
    2;
    4,    1;
    9,    5;
   22,   18,   1;
   56,   58,   8;
  145,  178,  41,  1;
  378,  532, 173, 11;
  988, 1563, 656, 73, 1;
  ...
T(6,2) = 8 since there are 8 flattened Catalan words of length 6 with 2 short peaks: 001010, 010100, 010101, 010010, 010120, 010121, 012010, and 012121.

Jean-Luc Baril, Pamela E. Harris, and José L. Ramírez, Flattened Catalan Words, arXiv:2405.05357 [math.CO], 2024. See pp. 19-20.

Cf. A007051 (row sums), A055588, A371965, A372883, A372884.

T[n_,k_]:=SeriesCoefficient[x(1-2x)/((1-x)(1-3x+x^2(1-y))),{x,0,n},{y,0,k}]; Table[T[n,k],{n,14},{k,0,Floor[(n-1)/2]}]//Flatten

G.f.: x*(1 - 2*x)/((1 - x)*(1 - 3*x + x^2*(1 - y))).
T(n,0) = A055588(n-1).
Sum_{k>=0} T(n,k) = A007051(n-1).

A377442 Square array read by rising antidiagonals: T(n, k) = A377441(-n, k), an extension of A377441 into the domain of negative n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 2, 4, 14, 1, 1, 2, 3, 9, 42, 1, 1, 2, 2, 6, 22, 132, 1, 1, 2, 1, 5, 12, 57, 429, 1, 1, 2, 0, 6, 6, 26, 154, 1430, 1, 1, 2, -1, 9, -2, 15, 59, 429, 4862, 1, 1, 2, -2, 14, -18, 24, 24, 138, 1223, 16796, 1, 1, 2, -3, 21, -48, 77, -23, 53, 332, 3550, 58786, 1, 1, 2, -4, 30, -98, 222, -226, 102, 107, 814, 10455, 208012, 1, 1, 2

Offset: 0

Thomas Scheuerle, Nov 04 2024

The main entry for this array is A377441.

			The array begins:
  [ 0] 1, 1, 2,  5, 14,  42,  132,   429,   1430, ... = A000108
  [-1] 1, 1, 2,  4,  9,  22,   57,   154,    429, ... = A105633
  [-2] 1, 1, 2,  3,  6,  12,   26,    59,    138, ... = A152172
  [-3] 1, 1, 2,  2,  5,   6,   15,    24,     53, ...
  [-4] 1, 1, 2,  1,  6,  -2,   24,   -23,    102, ...
  [-5] 1, 1, 2,  0,  9, -18,   77,  -226,    765, ...
  [-6] 1, 1, 2, -1, 14, -48,  222,  -921,   3914, ...
  [-7] 1, 1, 2, -2, 21, -98,  531, -2756,  14373, ...
Row index written as [m] is corresponding to A377441(m, k).

Cf. A377441 (The main entry for this sequence).
Cf. A105633 (row -1), A152172 (row -2).
Cf. A000108 (row 0), A254316 (row 1).
Cf. A000012 (Hankel transform of row 0), A006720 (Hankel transform of row 1).
Cf. A330025 (Hankel transform of row -1), A328380 (Hankel transform of row -2).
Cf. A371965, A377443.

A377443 Triangular array T(n,k) read by rows, satisfies A377441(n, k+2) = Sum_{m=0..k} T(k, m)*n^m.

Original entry on oeis.org

2, 5, 1, 14, 6, 1, 42, 27, 8, 1, 132, 111, 45, 10, 1, 429, 441, 222, 67, 12, 1, 1430, 1728, 1029, 382, 93, 14, 1, 4862, 6733, 4608, 2005, 599, 123, 16, 1, 16796, 26181, 20199, 10018, 3495, 881, 157, 18, 1, 58786, 101763, 87270, 48445, 19188, 5641, 1236, 195, 20, 1

Offset: 0

Thomas Scheuerle, Nov 04 2024

			Triangle T(n, k) starts:
[0]     2
[1]     5,      1
[2]    14,      6,     1
[3]    42,     27,     8,     1
[4]   132,    111,    45,    10,     1
[5]   429,    441,   222,    67,    12,    1
[6]  1430,   1728,  1029,   382,    93,   14,    1
[7]  4862,   6733,  4608,  2005,   599,  123,   16,   1
[8] 16796,  26181, 20199, 10018,  3495,  881,  157,  18,  1
[9] 58786, 101763, 87270, 48445, 19188, 5641, 1236, 195, 20, 1

Cf. A377441, A377442.
Cf. A254316 (row sums).
Cf. A000108, A091894, A175136, A371965.

A377441(n, max_k) = Vec(-2*((n+1)*x-1)/((x-1)*(n*x-1)+((n*x^2-(n+1)*x+1)^2-4*x*(x-1)*((n+1)*x-1)+O(x^max_k))^(1/2)))
T(n, k) = Vec(A377441(y, n+5)[n+3])[n-k+1]

A091894(n, k) = 2^(n-2*k-1)*binomial(n-1, 2*k)*(binomial(2*k, k)/(k + 1))
A175136(n, k) = sum(m=0,(n - k)/2,A091894(n-k, m)*binomial(n-m-1, n-k))
T(n, k) = sum(m=1, n+1-k, A175136(n+2-k, n-m+2-k)*binomial(m+k-1, m-1))+(k==0)

G.f.: (-(y*x^3-(y+1)*x^2+2*x+1) + sqrt((y*x^3-(y+1)*x^2+x)^2 - 4*(x^3-x^2)*((y+1)*x^2-x)))/(2*(x^3-x^2))/x^2.
T(n, 0) = A000108(n+2).
T(n, 1) = A371965(n+2).
T(n, 2) G.f.: x^2*1/( (x - 1)^2*(1 - 4*x)^(3/2) ).
T(n, 3) G.f.: x^3*(3*x - 1)/( (x - 1)^3*(1 - 4*x)^(5/2) ).
T(n, 4) G.f.: x^4*(x^3 + (3*x - 1)^2)/( (x - 1)^4*(1 - 4*x)^(7/2) ).
T(n, 5) G.f.: x^5*(3*x^3*(3*y - 1) + (3*x - 1)^3)/( (x - 1)^5*(1 - 4*x)^(9/2) ).
T(n, 6) G.f.: x^6*(2*x^6 + 6*x^3*(3*x - 1)^2 + (3*x - 1)^4)/( (x - 1)^6*(1 - 4*x)^(11/2) ).
T(n, 7) G.f.: x^7*(10*x^6*(3*x - 1) + 10*x^3*(3*x - 1)^3 + (3*x - 1)^5)/( (x - 1)^7*(1 - 4*x)^(13/2) ).
0 = Sum_{n=0..k} T(n+k, n)*(-1)^n*binomial(k, n).
The diagonal k terms below main diagonal has G.f.: 1 + Sum_{m=1..k+1} A175136(k+2, k-m+2)*(1 - x)^k.
T(n+k, n) = Sum_{m=1..k+1} A175136(k+2, k-m+2)*binomial(m+n-1, m-1), for k > 0.

cp's OEIS Frontend

A371963 a(n) is the sum of all valleys in the set of Catalan words of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A371964 a(n) is the sum of all symmetric valleys in the set of Catalan words of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A275289 Number of set partitions of [n] with symmetric block size list of length three.

Views

Author

Keywords

Links

Crossrefs

Formula

A372883 Irregular triangle read by rows: T(n,k) is the number of flattened Catalan words of length n with exactly k symmetric peaks, with k >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A377441 Square array T(n, k) read by rising antidiagonals. Row n has the ordinary generating function (-(n*x^3-(n+1)*x^2+x) + sqrt((n*x^3-(n+1)*x^2+x)^2 - 4*(x^3-x^2)*((n+1)*x^2-x)))/(2*(x^3-x^2)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A372879 Irregular triangle read by rows: T(n,k) is the number of flattened Catalan words of length n with exactly k short peak, with k >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A377442 Square array read by rising antidiagonals: T(n, k) = A377441(-n, k), an extension of A377441 into the domain of negative n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A377443 Triangular array T(n,k) read by rows, satisfies A377441(n, k+2) = Sum_{m=0..k} T(k, m)*n^m.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

PARI

Formula

A377441 Square array T(n, k) read by rising antidiagonals. Row n has the ordinary generating function (-(nx^3-(n+1)x^2+x) + sqrt((nx^3-(n+1)x^2+x)^2 - 4(x^3-x^2)((n+1)x^2-x)))/(2(x^3-x^2)).