A048285 -id:A048285 - cp's OEIS frontend

A239528 Decimal expansion of a constant related to A048285.

1, 1, 9, 9, 7, 6, 5, 1, 2, 7, 4, 8, 0, 7, 7, 8, 9, 6, 7, 3, 0, 4, 9, 8, 4, 0, 0, 4, 3, 1, 2, 9, 2, 0, 7, 6, 2, 8, 2, 0, 7, 0, 5, 1, 9, 3, 3, 4, 7, 8, 6, 3, 4, 7, 1, 6, 2, 0, 7, 7, 4, 0, 4, 9, 6, 9, 2, 7, 1, 4, 7, 6, 2, 0, 7, 5, 6, 3, 4, 7, 4, 8, 1, 7, 2, 5, 9, 1, 4, 4, 0, 6, 7, 9, 3, 1, 5, 4, 2, 8, 0, 2, 1, 9, 0, 7

Offset: 0

Vaclav Kotesovec, Mar 21 2014

			0.11997651274807789673049840043129207628207...

J. G. Penaud and O. Roques, Génération de chemins de Dyck à pics croissants, Discrete Mathematics, Vol. 246, no. 1-3 (2002), 255-267.

Cf. A048285.

RealDigits[N[(Sqrt[5]-3)/(Sqrt[5]-5)*Sum[(-1)^k*x^(2*k)/Product[(1-x)*(1-x^i)-x,{i,2,k+1}],{k,0,300}]/.x->(3-Sqrt[5])/2,60]][[1]]

Equals lim n->infinity A048285(n)/((3+sqrt(5))/2)^n.

A008930 Number of compositions (p_1, p_2, p_3, ...) of n with 1 <= p_i <= i for all i.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 21, 41, 80, 157, 310, 614, 1218, 2421, 4819, 9602, 19147, 38204, 76266, 152307, 304256, 607941, 1214970, 2428482, 4854630, 9705518, 19405030, 38800412, 77585314, 155145677, 310251190, 620437691, 1240771141, 2481374234

Offset: 0

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)

nonn

a(n) is the number of compositions (p_1,p_2,...) of n with 1<=p_i<=i for all i. a(n) is the number of Dyck n-paths with strictly increasing peaks. To get the correspondence, given such a Dyck path, split the path after the first up step reaching height i, i=1,2,...,h where h is the path's maximum height and count up steps in each block. Example: U-U-DUU-U-DDDD has been split as specified, yielding the composition (1,1,2,1). - David Callan, Feb 18 2004

Row sums of triangle A177517.

			G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 11*x^6 + 21*x^7 + ...
The g.f. equals the following series involving q-factorials:
A(x) = 1 + x + x^2*(1+x) + x^3*(1+x)*(1+x+x^2) + x^4*(1+x)*(1+x+x^2)*(1+x+x^2+x^3) + x^5*(1+x)*(1+x+x^2)*(1+x+x^2+x^3)*(1+x+x^2+x^3+x^4) + ...
From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(7)=21 compositions p(1)+p(2)+...+p(m) = 7 such that p(k) <= k:
  [ 1]  [ 1 1 1 1 1 1 1 ]
  [ 2]  [ 1 1 1 1 1 2 ]
  [ 3]  [ 1 1 1 1 2 1 ]
  [ 4]  [ 1 1 1 1 3 ]
  [ 5]  [ 1 1 1 2 1 1 ]
  [ 6]  [ 1 1 1 2 2 ]
  [ 7]  [ 1 1 1 3 1 ]
  [ 8]  [ 1 1 1 4 ]
  [ 9]  [ 1 1 2 1 1 1 ]
  [10]  [ 1 1 2 1 2 ]
  [11]  [ 1 1 2 2 1 ]
  [12]  [ 1 1 2 3 ]
  [13]  [ 1 1 3 1 1 ]
  [14]  [ 1 1 3 2 ]
  [15]  [ 1 2 1 1 1 1 ]
  [16]  [ 1 2 1 1 2 ]
  [17]  [ 1 2 1 2 1 ]
  [18]  [ 1 2 1 3 ]
  [19]  [ 1 2 2 1 1 ]
  [20]  [ 1 2 2 2 ]
  [21]  [ 1 2 3 1 ]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3324 (first 201 terms from Vincenzo Librandi)
Margaret Archibald, Aubrey Blecher, Arnold Knopfmacher, and Stephan Wagner, Subdiagonal and superdiagonal compositions, Art Disc. Appl. Math. (2024). See p. 5.
Roland Bacher, Generic numerical semigroups, hal-03221466 [math.CO], 2021.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
M. Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121.

Cf. A000707, A048285, A177517.

b:= proc(n, i) option remember; `if`(i>=n,
      ceil(2^(n-1)), add(b(n-j, i+1), j=1..min(i, n)))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..50);  # Alois P. Heinz, Mar 25 2014, revised Jun 26 2023

Sum[x^n*Product[(1-x^k)/(1-x), {k, 1, n}], {n, 0, 40}]+O[x]^41
Table[SeriesCoefficient[1+Sum[x^j*Product[(1-x^k)/(1-x),{k,1,j}],{j,1,n}],{x,0,n}],{n,0,40}] (* Vaclav Kotesovec, Mar 17 2014 *)
b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[b[n-j, i+1], {j, 1, Min[i, n]}]]; a[n_] := b[n, 1]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 15 2015, after Alois P. Heinz *)

{ n=8; v=vector(n); for (i=1,n,v[i]=vector(i!)); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, for (a=0,i-1, v[i][j+a*k]=v[i-1][j]+a+1))); c=vector(n); for (i=1,n, for (j=1,i!, if (v[i][j]<=n, c[v[i][j]]++))); c } \\ Jon Perry

N=66; q='q+O('q^N); Vec( sum(n=0,N, q^n * prod(k=1,n, (1-q^k)/(1-q) ) ) ) \\ Joerg Arndt, Mar 24 2014

G.f.: A(x) = Sum_{n>=0} x^n * Product_{k=1..n} (1-x^k)/(1-x). - Paul D. Hanna, Mar 20 2003
G.f.: A(x) = 1/(1 - x/(1+x) /(1 - x/(1+x+x^2) /(1 - x/(1+x+x^2+x^3) /(1 - x/(1+x+x^2+x^3+x^4) /(1 - x/(1+x+x^2+x^3+x^4+x^5) /(1 -...)))))), a continued fraction. - Paul D. Hanna, May 15 2012
Limit_{n->oo} a(n+1)/a(n) = 2. - Mats Granvik, Feb 22 2011
a(n) ~ c * 2^(n-1), where c = 0.288788095086602421... (see constant A048651). - Vaclav Kotesovec, Mar 17 2014

More terms from Paul D. Hanna, Mar 20 2003
Offset corrected to 0 by Joerg Arndt, Mar 24 2014
New name (using comment by David Callan) from Joerg Arndt, Mar 25 2014

A281874 Number of Dyck paths of semilength n with distinct peak heights.

Original entry on oeis.org

1, 1, 1, 3, 5, 13, 31, 71, 181, 447, 1111, 2799, 7083, 17939, 45563, 115997, 295827, 755275, 1929917, 4935701, 12631111, 32340473, 82837041, 212248769, 543978897, 1394481417, 3575356033, 9168277483, 23512924909, 60306860253, 154689354527, 396809130463

Offset: 0

David Callan, Jan 31 2017

nonn

a(n) is the number of Dyck paths of length 2n with no two peaks at the same height. A peak is a UD, an up-step U=(1,1) immediately followed by a down-step D=(1,-1).
In the Mathematica recurrence below, a(n,k) is the number of Dyck paths of length 2n with all peaks at distinct heights except that there are k peaks at the maximum peak height. Thus a(n)=a(n,1). The recurrence is based on the following simple observation. Paths counted by a(n,k) are obtained from paths counted by a(n-k,i) for some i, 1<=i<=k+1, by inserting runs of one or more contiguous peaks at each of the existing peak vertices at the maximum peak height, except that (at most) one such existing peak may be left undisturbed, and so that a total of k new peaks are added.
It appears that lim a(n)/a(n-1) as n approaches infinity exists and is approximately 2.5659398.

			a(3)=3 counts UUUDDD, UDUUDD, UUDDUD because the first has only one peak and the last two have peak heights 1,2 and 2,1 respectively.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 19.

A048285 counts Dyck paths with nondecreasing peak heights.
Column k=1 of A287847, A288108.
Cf. A287846, A287901, A289020.

a[n_, k_] /; k == n := 1;
a[n_, k_] /; (k > n || k < 1) := 0;
a[n_, k_] :=
a[n, k] =
  Sum[(Binomial[k - 1, i - 1] + i Binomial[k - 1, i - 2]) a[n - k,
     i], {i, k + 1}];
Table[a[n, 1], {n, 28}]

A288140 Number of Dyck paths of semilength n such that the number of peaks is weakly decreasing from lower to higher levels.

Original entry on oeis.org

1, 1, 1, 3, 4, 12, 28, 63, 177, 455, 1233, 3383, 9359, 26809, 77078, 223201, 653982, 1934508, 5783712, 17431660, 52879184, 161386859, 495432345, 1530191918, 4754079840, 14849407892, 46604383972, 146897291083, 464892421363, 1477052536749, 4711124635655

Offset: 0

Alois P. Heinz, Jun 05 2017

nonn

			. a(5) = 12:
.                       /\         /\         /\
.   /\/\/\/\/\   /\/\/\/  \   /\/\/  \/\   /\/  \/\/\
.
.    /\               /\/\       /\/\       /\/\
.   /  \/\/\/\   /\/\/    \   /\/    \/\   /    \/\/\
.
.         /\         /\           /\         /\
.      /\/  \       /  \/\     /\/  \       /  \/\
.   /\/      \   /\/      \   /      \/\   /      \/\  .

Alois P. Heinz, Table of n, a(n) for n = 0..200
Wikipedia, Counting lattice paths

Cf. A000108, A008930, A048285, A288141, A288146, A288147.

b:= proc(n, k, j) option remember; `if`(n=j, 1, add(add(
       b(n-j, t, i)*binomial(i, t)*binomial(j-1, i-1-t),
       t=max(k, i-j)..min(n-j, i-1)), i=1..n-j))
    end:
a:= n-> `if`(n=0, 1, add(b(n, k$2), k=1..n)):
seq(a(n), n=0..31);

b[n_, k_, j_] := b[n, k, j] = If[n == j, 1, Sum[Sum[b[n - j, t, i]* Binomial[i, t]*Binomial[j - 1, i - 1 - t], {t, Max[k, i - j], Min[n - j, i - 1]}], {i, 1, n - j}]];
a[n_] := If[n == 0, 1, Sum[b[n, k, k], {k, 1, n}]];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, May 29 2018, from Maple *)

A288141 Number of Dyck paths of semilength n such that the number of peaks is strongly decreasing from lower to higher levels.

Original entry on oeis.org

1, 1, 1, 1, 4, 5, 10, 22, 46, 148, 324, 722, 1843, 4634, 12537, 34248, 95711, 266761, 724689, 1983267, 5553902, 15900083, 46201546, 135511171, 400668869, 1189723253, 3535186203, 10516298421, 31405658622, 94378367065, 285623516777, 870481565252, 2671088133010

Offset: 0

Alois P. Heinz, Jun 05 2017

nonn

			a(5) = 5:
                     /\        /\        /\        /\
  /\/\/\/\/\  /\/\/\/  \  /\/\/  \/\  /\/  \/\/\  /  \/\/\/\

Alois P. Heinz, Table of n, a(n) for n = 0..200
Wikipedia, Counting lattice paths

Cf. A000108, A008930, A048285, A288140, A288146, A288147.

b:= proc(n, k, j) option remember; `if`(n=j, 1, add(add(
       b(n-j, t, i)*binomial(i, t)*binomial(j-1, i-1-t),
       t=max(k+1, i-j)..min(n-j, i-1)), i=1..n-j))
    end:
a:= n-> `if`(n=0, 1, add(b(n, k$2), k=1..n)):
seq(a(n), n=0..34);

b[n_, k_, j_] := b[n, k, j] = If[n == j, 1, Sum[Sum[b[n - j, t, i]* Binomial[i, t]*Binomial[j - 1, i - 1 - t], {t, Max[k + 1, i - j], Min[n - j, i - 1]}], {i, 1, n - j}]];
a[n_] := If[n == 0, 1, Sum[b[n, k, k], {k, 1, n}]];
Table[a[n], {n, 0, 34}] (* Jean-François Alcover, May 29 2018, from Maple *)

A288146 Number of Dyck paths of semilength n such that the number of peaks is weakly increasing from lower to higher levels and no positive level is peakless.

Original entry on oeis.org

1, 1, 1, 3, 3, 13, 28, 65, 199, 540, 1468, 4188, 12328, 36870, 110181, 331226, 1012241, 3137822, 9796834, 30695164, 96658857, 306575170, 979485119, 3148413910, 10169223709, 32983822120, 107413795300, 351235602807, 1153308804255, 3802294411213, 12581993628872

Offset: 0

Alois P. Heinz, Jun 05 2017

nonn

			a(3) = 3:
                           /\       /\
             /\/\/\     /\/  \     /  \/\
a(4) = 3:
                          /\/\     /\/\
            /\/\/\/\   /\/    \   /    \/\

Alois P. Heinz, Table of n, a(n) for n = 0..200
Wikipedia, Counting lattice paths

Cf. A000108, A008930, A048285, A288140, A288141, A288147.

b:= proc(n, k, j) option remember; `if`(n=j, 1, add(add(
       b(n-j, t, i)*binomial(i, t)*binomial(j-1, i-1-t),
       t=max(1, i-j)..min(k, n-j, i-1)), i=1..n-j))
    end:
a:= n-> `if`(n=0, 1, add(b(n, k$2), k=1..n)):
seq(a(n), n=0..34);

b[n_, k_, j_] := b[n, k, j] = If[n == j, 1, Sum[Sum[b[n - j, t, i]* Binomial[i, t]*Binomial[j - 1, i - 1 - t], {t, Max[1, i - j], Min[k, n - j, i - 1]}], {i, 1, n - j}]];
a[n_] := If[n == 0, 1, Sum[b[n, k, k], {k, 1, n}]];
Table[a[n], {n, 0, 34}] (* Jean-François Alcover, May 29 2018, from Maple *)

A288147 Number of Dyck paths of semilength n such that the number of peaks is strongly increasing from lower to higher levels and no positive level is peakless.

Original entry on oeis.org

1, 1, 1, 1, 3, 6, 12, 31, 68, 186, 506, 1299, 3481, 9712, 27692, 79587, 232743, 694896, 2086245, 6248158, 18771510, 57007483, 175149700, 542313513, 1688360997, 5288335561, 16679137617, 52933231538, 168768966207, 539981776609, 1733555552587, 5587076558809

Offset: 0

Alois P. Heinz, Jun 05 2017

nonn

			a(5) = 6:
                     /\  /\      /\    /\
    /\/\/\/\/\    /\/  \/  \    /  \/\/  \
.
     /\  /\          /\/\/\      /\/\/\
    /  \/  \/\    /\/      \    /      \/\

Alois P. Heinz, Table of n, a(n) for n = 0..200
Wikipedia, Counting lattice paths

Cf. A000108, A008930, A048285, A288140, A288141, A288146.

b:= proc(n, k, j) option remember; `if`(n=j, 1, add(add(
       b(n-j, t, i)*binomial(i, t)*binomial(j-1, i-1-t),
       t=max(1, i-j)..min(k-1, n-j, i-1)), i=1..n-j))
    end:
a:= n-> `if`(n=0, 1, add(b(n, k$2), k=1..n)):
seq(a(n), n=0..34);

b[n_, k_, j_] := b[n, k, j] = If[n == j, 1, Sum[Sum[b[n - j, t, i]* Binomial[i, t]*Binomial[j - 1, i - 1 - t], {t, Max[1, i - j], Min[k - 1, n - j, i - 1]}], {i, 1, n - j}]];
a[n_] := If[n == 0, 1, Sum[b[n, k, k], {k, 1, n}]];
Table[a[n], {n, 0, 34}] (* Jean-François Alcover, May 29 2018, from Maple *)

A138155 Triangle read by rows: T(n,k) is the number of Dyck paths with nondecreasing peaks having semilength n and with height of last peak equal to k (1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 7, 8, 4, 1, 1, 12, 19, 13, 5, 1, 1, 20, 42, 37, 19, 6, 1, 1, 33, 89, 97, 62, 26, 7, 1, 1, 54, 183, 240, 184, 95, 34, 8, 1, 1, 88, 368, 570, 511, 312, 137, 43, 9, 1, 1, 143, 728, 1312, 1351, 951, 491, 189, 53, 10, 1

Offset: 1

Emeric Deutsch, Mar 04 2008

Row sums yield A048285.
T(n,2) = A000071(n+1) (Fibonacci numbers - 1).
T(n,3) = A095681(n-3).

			T(2,1)=1 because we have /\/\.
T(5,4)=4 because we have UDUUUUDDDD, UUDUUUDDDD, UUUDUUDDDD and UUUUDUDDDD, where U=(1,1) and D=(1,-1).
Triangle T(n,k) begins:
1;
1,  1;
1,  2,   1;
1,  4,   3,   1;
1,  7,   8,   4,   1;
1, 12,  19,  13,   5,  1;
1, 20,  42,  37,  19,  6,  1;
1, 33,  89,  97,  62, 26,  7, 1;
1, 54, 183, 240, 184, 95, 34, 8, 1;

Alois P. Heinz, Rows n = 1..141, flattened
J. G. Penaud and O. Roques, Génération de chemins de Dyck à pics croissants, Discrete Mathematics, Vol. 246, no. 1-3 (2002), 255-267.

Cf. A000071, A048285, A095681.

g:=sum((-1)^n*t*z^(2*n+1)*(1-z)/(product((1-z)*(1-t*z^i)-z,i=1..n+1)), n=0.. 30): gser:=simplify(series(g,z=0,15)): for n to 11 do P[n]:=sort(coeff(gser, z,n)) end do: for n to 11 do seq(coeff(P[n],t,j),j=1..n) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, k, t) option remember; `if`(x=0, z^k,
      `if`(t and yx, 0, b(x-1, y+1, k, true)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=1..n))(b(2*n, 0$2, true)):
seq(T(n), n=1..12);  # Alois P. Heinz, Apr 02 2017

b[x_, y_, k_, t_] := b[x, y, k, t] = If[x==0, z^k, If[t && y x, 0, b[x-1, y+1, k, True]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 1, n}]][b[2*n, 0, 0, True]];
Array[T, 12] // Flatten (* Jean-François Alcover, Jun 19 2018, from Alois P. Heinz's 2nd Maple program *)

G.f.: Sum_{n >= 0} {(-1)^n tz^{2n+1}(1-z)}/ {Product_{i=1...n+1}((1-z)(1-tz^i)-z)}.

Conjectural g.f.: Sum_{n>=1} (t*x*(1 - x))^n/( Product_{i=2..n+1} (1 - 2*x + x^i) ) = t*x + (t + t^2)*x^2 + (t + 2*t^2 + t^3)*x^3 + ... (checked up to x^12). - Peter Bala, Mar 31 2017

cp's OEIS Frontend

A239528 Decimal expansion of a constant related to A048285.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A008930 Number of compositions (p_1, p_2, p_3, ...) of n with 1 <= p_i <= i for all i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A281874 Number of Dyck paths of semilength n with distinct peak heights.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A288140 Number of Dyck paths of semilength n such that the number of peaks is weakly decreasing from lower to higher levels.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A288141 Number of Dyck paths of semilength n such that the number of peaks is strongly decreasing from lower to higher levels.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A288146 Number of Dyck paths of semilength n such that the number of peaks is weakly increasing from lower to higher levels and no positive level is peakless.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A288147 Number of Dyck paths of semilength n such that the number of peaks is strongly increasing from lower to higher levels and no positive level is peakless.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A138155 Triangle read by rows: T(n,k) is the number of Dyck paths with nondecreasing peaks having semilength n and with height of last peak equal to k (1 <= k <= n).

Views

Author

Keywords