A258109 -id:A258109 - cp's OEIS frontend

A080936 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and height k (1 <= k <= n).

1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 15, 18, 7, 1, 1, 31, 57, 33, 9, 1, 1, 63, 169, 132, 52, 11, 1, 1, 127, 482, 484, 247, 75, 13, 1, 1, 255, 1341, 1684, 1053, 410, 102, 15, 1, 1, 511, 3669, 5661, 4199, 1975, 629, 133, 17, 1, 1, 1023, 9922, 18579, 16017, 8778, 3366, 912, 168, 19, 1

Offset: 1

Henry Bottomley, Feb 25 2003

Sum of entries in row n is A000108(n) (the Catalan numbers).
From Gus Wiseman, Nov 16 2022: (Start)
Also the number of unlabeled ordered rooted trees with n nodes and height k. For example, row n = 5 counts the following trees:
  (oooo)  ((o)oo)   (((o))o)  ((((o))))
          ((oo)o)   (((o)o))
          ((ooo))   (((oo)))
          (o(o)o)   ((o(o)))
          (o(oo))   (o((o)))
          (oo(o))
          ((o)(o))
(End)

			T(3,2)=3 because we have UUDDUD, UDUUDD, and UUDUDD, where U=(1,1) and D=(1,-1). The other two Dyck paths of semilength 3, UDUDUD and UUUDDD, have heights 1 and 3, respectively. - _Emeric Deutsch_, Jun 08 2011
Triangle starts:
  1;
  1,  1;
  1,  3,   1;
  1,  7,   5,   1;
  1, 15,  18,   7,  1;
  1, 31,  57,  33,  9,  1;
  1, 63, 169, 132, 52, 11, 1;

N. G. de Bruijn, D. E. Knuth, and S. O. Rice, The average height of planted plane trees, in: Graph Theory and Computing (ed. T. C. Read), Academic Press, New York, 1972, pp. 15-22.

Alois P. Heinz, Rows n = 1..141, flattened
Tomás Aguilar-Fraga, Jennifer Elder, Rebecca E. Garcia, Kimberly P. Hadaway, Pamela E. Harris, Kimberly J. Harry, Imhotep B. Hogan, Jakeyl Johnson, Jan Kretschmann, Kobe Lawson-Chavanu, J. Carlos Martínez Mori, Casandra D. Monroe, Daniel Quiñonez, Dirk Tolson III, and Dwight Anderson Williams II, Interval and L-interval Rational Parking Functions, arXiv:2311.14055 [math.CO], 2023. See p. 11.
FindStat - Combinatorial Statistic Finder, The height of a Dyck path
FindStat - Combinatorial Statistic Finder, The height of a Dyck path., The depth of an ordered tree., The depth minus 1 of an ordered tree
Anthony Joseph and Polyxeni Lamprou, A new interpretation of Catalan numbers, arXiv preprint arXiv:1512.00406 [math.CO], 2015.
Germain Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
Germain Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
Kevin Limanta, Hopein Christofen Tang, and Yozef Tjandra, Permutation-generated maps between Dyck paths, arXiv:2105.14439 [math.CO], 2021. Mentions this sequence.
Dimana Miroslavova Pramatarova, Investigating the Periodicity of Weighted Catalan Numbers and Generalizing Them to Higher Dimensions, MIT Res. Sci. Instit. (2025). See p. 13.
Thomas Tunstall, Tim Rogers, and Wolfram Möbius, Assisted percolation of slow-spreading mutants in heterogeneous environments, arXiv:2303.01579 [q-bio.PE], 2023.
Vince White, Enumeration of Lattice Paths with Restrictions, (2024). Electronic Theses and Dissertations. 2799. See pp. 19, 25.

Cf. A000108 (row sums), A079214, A080934, A080935, A259885, A259899, A289481.
Columns k=1-10 give: A000012, A000225(n-1), A258109, A262600, A289418, A289419, A289420, A289421, A289422, A289423.
T(2n,n) gives A268316.
Counting by leaves instead of height gives A001263.
The unordered version is A034781.
The height statistic is ranked by A358379, unordered A109082.
Cf. A000081, A005043, A032027, A284778.

f := proc (k) options operator, arrow:
   sum(binomial(k-i, i)*(-z)^i, i = 0 .. floor((1/2)*k))
end proc:
h := proc (k) options operator, arrow:
   z^k/(f(k)*f(k+1))
end proc:
T := proc (n, k) options operator, arrow:
   coeff(series(h(k), z = 0, 25), z, n)
end proc:
for n to 11 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form Emeric Deutsch, Jun 08 2011
# second Maple program:
b:= proc(x, y, k) option remember; `if`(y>min(k, x) or y<0, 0,
      `if`(x=0, 1, b(x-1, y-1, k)+ b(x-1, y+1, k)))
    end:
T:= (n, k)-> b(2*n, 0, k) -`if`(k=0, 0, b(2*n, 0, k-1)):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Aug 06 2012

b[x_, y_, k_] := b[x, y, k] = If[y > Min[k, x] || y<0, 0, If[x == 0, 1, b[x-1, y-1, k] + b[x-1, y+1, k]]]; T[n_, k_] := b[2*n, 0, k] - If[k == 0, 0, b[2*n, 0, k-1] ]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Feb 26 2015, after Alois P. Heinz *)
aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n],Depth[#]-2==k&]],{n,1,9},{k,1,n-1}] (* Gus Wiseman, Nov 16 2022 *)

T(n, k) = A080934(n, k) - A080934(n, k-1).
The g.f. for Dyck paths of height k is h(k) = z^k/(f(k)*f(k+1)), where f(k) are Fibonacci type polynomials defined by f(0)=f(1)=1, f(k)=f(k-1)-z*f(k-2) or by f(k) = Sum_{i=0..floor(k/2)} binomial(k-i,i)*(-z)^i. Incidentally, the g.f. for Dyck paths of height at most k is H(k) = f(k)/f(k+1). - Emeric Deutsch, Jun 08 2011
For all n >= 1 and floor((n+1)/2) <= k <= n we have: T(n,k) = 2*(2*k+3)*(2*k^2+6*k+1-3*n)*(2*n)!/((n-k)!*(n+k+3)!). - Gheorghe Coserea, Dec 06 2015
T(n, k) = Sum_{i=1..k-1} (-1)^(i+1) * (Sum_{j=1..n} (Sum_{x=0..n} (-1)^(j+x) * binomial(x+2n-2j+1,x))) * a(k-i); a(1)=1, a(0)=0. - Tim C. Flowers, May 14 2018

A287213 Number T(n,k) of set partitions of [n] such that the maximal absolute difference between consecutive elements within a block equals k; triangle T(n,k), n>=0, 0<=k<=max(n-1,0), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 7, 5, 2, 1, 15, 18, 13, 5, 1, 31, 57, 61, 38, 15, 1, 63, 169, 248, 215, 129, 52, 1, 127, 482, 935, 1061, 836, 495, 203, 1, 255, 1341, 3368, 4835, 4789, 3573, 2108, 877, 1, 511, 3669, 11777, 20973, 25430, 22986, 16657, 9831, 4140

Offset: 0

Alois P. Heinz, May 21 2017

The maximal absolute difference is assumed to be zero if there is no block with consecutive elements.

T(n,k) is defined for all n,k >= 0. The triangle contains only the positive terms. T(n,k) = 0 if k>=n and k>0.

			T(4,0) = 1: 1|2|3|4.
T(4,1) = 7: 1234, 123|4, 12|34, 12|3|4, 1|234, 1|23|4, 1|2|34.
T(4,2) = 5: 124|3, 134|2, 13|24, 13|2|4, 1|24|3.
T(4,3) = 2: 14|23, 14|2|3.
Triangle T(n,k) begins:
  1;
  1;
  1,   1;
  1,   3,   1;
  1,   7,   5,   2;
  1,  15,  18,  13,    5;
  1,  31,  57,  61,   38,  15;
  1,  63, 169, 248,  215, 129,  52;
  1, 127, 482, 935, 1061, 836, 495, 203;

Alois P. Heinz, Rows n = 0..23, flattened
Wikipedia, Partition of a set

Columns k=0-10 give: A000012, A000225(n-1), A258109, A294052, A294053, A294054, A294055, A294056, A294057, A294058, A294059.
Row sums and T(n+2,n+1) give A000110.
T(2n,n) gives A294024.
Cf. A287214, A287215, A287416, A287640.

b:= proc(n, k, l) option remember; `if`(n=0, 1, b(n-1, k, map(x->
      `if`(x-n>=k, [][], x), [l[], n]))+add(b(n-1, k, sort(map(x->
      `if`(x-n>=k, [][], x), subsop(j=n, l)))), j=1..nops(l)))
    end:
A:= (n, k)-> b(n, min(k, n-1), []):
T:= (n, k)-> A(n, k)-`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..max(n-1, 0)), n=0..12);

b[0, , ] = 1; b[n_, k_, l_] := b[n, k, l] =b[n - 1, k, If[# - n >= k, Nothing, #]& /@ Append[l, n]] + Sum[b[n - 1, k, Sort[If[# - n >= k, Nothing, #]& /@ ReplacePart[l, j -> n]]], {j, 1, Length[l]}];
A[n_, k_] := b[n, Min[k, n - 1], {}];
T[n_, k_] :=  A[n, k] - If[k == 0, 0, A[n, k - 1]];
Table[Table[T[n, k], {k, 0, Max[n - 1, 0]}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Apr 30 2018, after Alois P. Heinz *)

T(n,k) = A287214(n,k) - A287214(n,k-1) for k>0, T(n,0) = 1.

A105693 a(n) = Fibonacci(2n+2)-2^n.

Original entry on oeis.org

0, 1, 4, 13, 39, 112, 313, 859, 2328, 6253, 16687, 44320, 117297, 309619, 815656, 2145541, 5637351, 14799280, 38826025, 101809867, 266865720, 699311581, 1832117599, 4799138368, 12569491809, 32917725667, 86200462408, 225717215989, 591018294423, 1547471885008

Offset: 0

Paul Barry, Apr 17 2005

Colin Barker, Table of n, a(n) for n = 0..1000
E. Czabarka et al, Enumerations of peaks and valleys on non-decreasing Dyck paths, Disc. Math. 341 (2018) 2789-2807. See Table 4.
Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 15, 17, 19.
Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 22.
Index entries for linear recurrences with constant coefficients, signature (5,-7,2).

Cf. A000045, A061667, A001906, A258109.

[Fibonacci(2*n+2)-2^n: n in [0..30]]; // Vincenzo Librandi, Apr 21 2011

Table[Fibonacci[2n+2]-2^n,{n,0,30}] (* or *) LinearRecurrence[{5,-7,2},{0,1,4},40] (* Harvey P. Dale, Jul 21 2016 *)

concat(0, Vec(x*(1-x)/((1-2*x)*(1-3*x+x^2)) + O(x^40))) \\ Colin Barker, Sep 12 2016

a(n)=fibonacci(2*n+2)-2^n \\ Charles R Greathouse IV, Sep 12 2016

G.f.: x(1-x)/((1-2x)(1-3x+x^2)).
a(n) = sum{k=0..n+1, binomial(n+1, k+1)*sum{j=0..floor(k/2), F(k-2j)}}.
a(n) = A258109(n+1) + A001906(n), n>1. - Yuriy Sibirmovsky, Sep 12 2016
a(n) = 5*a(n-1)-7*a(n-2)+2*a(n-3) for n>2. - Colin Barker, Sep 12 2016

A276472 Modified Pascal's triangle read by rows: T(n,k) = T(n-1,k) + T(n-1,k-1), 12. T(n,n) = T(n,n-1) + T(n-1,n-1), n>1. T(1,1) = 1, T(2,1) = 1. n>=1.

Original entry on oeis.org

1, 1, 2, 4, 3, 5, 11, 7, 8, 13, 29, 18, 15, 21, 34, 76, 47, 33, 36, 55, 89, 199, 123, 80, 69, 91, 144, 233, 521, 322, 203, 149, 160, 235, 377, 610, 1364, 843, 525, 352, 309, 395, 612, 987, 1597, 3571, 2207, 1368, 877, 661, 704, 1007, 1599, 2584, 4181

Offset: 1

Yuriy Sibirmovsky, Sep 12 2016

The recurrence relations for the border terms are the only way in which this differs from Pascal's triangle.
Column T(2n,n+1) appears to be divisible by 4 for n>=2; T(2n-1,n) divisible by 3 for n>=2; T(2n,n-2) divisible by 2 for n>=3.
The symmetry of T(n,k) can be observed in a hexagonal arrangement (see the links).
Consider T(n,k) mod 3 = q. Terms with q = 0 show reflection symmetry with respect to the central column T(2n-1,n), while q = 1 and q = 2 are mirror images of each other (see the link).

			Triangle T(n,k) begins:
n\k 1    2    3    4   5    6    7    8    9
1   1
2   1    2
3   4    3    5
4   11   7    8    13
5   29   18   15   21   34
6   76   47   33   36   55   89
7   199  123  80   69   91   144 233
8   521  322  203  149  160  235 377  610
9   1364 843  525  352  309  395 612  987  1597
...
In another format:
__________________1__________________
_______________1_____2_______________
____________4_____3_____5____________
________11_____7_____8_____13________
____29_____18_____15____21_____34____
_76_____47____33_____36____55_____89_

Yuriy Sibirmovsky, T(n,k), read by rows as a linear sequence a(j) for j = 1..5050
Yuriy Sibirmovsky, Symmetrical hexagonal arrangement for initial terms of T(n,k)
Yuriy Sibirmovsky, T(n,k) compared with Pascal's triangle
Yuriy Sibirmovsky, Illustration for T(n,k) mod 3

Cf. A000045, A000204, A001519, A001906, A002878, A005248, A054441, A088305, A122367, A258109, A026671, A026726, A026732, A004187, A049685, A033891, A206351, A092521, A081018, A049684, A058038, A081016, A003482, A049629, A133273, A049664, A049683, A119032, A023039, A007805, A033889.

Nm=12;
T=Table[0,{n,1,Nm},{k,1,n}];
T[[1,1]]=1;
T[[2,1]]=1;
T[[2,2]]=2;
Do[T[[n,1]]=T[[n-1,1]]+T[[n,2]];
T[[n,n]]=T[[n-1,n-1]]+T[[n,n-1]];
If[k!=1&&k!=n,T[[n,k]]=T[[n-1,k]]+T[[n-1,k-1]]],{n,3,Nm},{k,1,n}];
{Row[#,"\t"]}&/@T//Grid

T(n,k) = if (k==1, if (n==1, 1, if (n==2, 1, T(n-1,1) + T(n,2))), if (kMichel Marcus, Sep 14 2016

Conjectures:
Relations with other sequences:
T(n+1,1) = A002878(n-1), n>=1.
T(n,n) = A001519(n) = A122367(n-1), n>=1.
T(n+1,2) = A005248(n-1), n>=1.
T(n+1,n) = A001906(n) = A088305(n), n>=1.
T(2n-1,n) = 3*A054441(n-1), n>=2. [the central column].
Sum_{k=1..n} T(n,k) = 3*A105693(n-1), n>=2. [row sums].
Sum_{k=1..n} T(n,k)-T(n,1)-T(n,n) = 3*A258109(n), n>=2.
T(2n,n+1) - T(2n,n) = A026671(n), n>=1.
T(2n,n-1) - T(2n,n) = 2*A026726(n-1), n>=2.
T(n,ceiling(n/2)) - T(n-1,floor(n/2)) = 2*A026732(n-3), n>=3.
T(2n+1,2n) = 3*A004187(n), n>=1.
T(2n+1,2) = 3*A049685(n-1), n>=1.
T(2n+1,2n) + T(2n+1,2) = 3*A033891(n-1), n>=1.
T(2n+1,3) = 5*A206351(n), n>=1.
T(2n+1,2n)/3 - T(2n+1,3)/5 = 4*A092521(n-1), n>=2.
T(2n,1) = 1 + 5*A081018(n-1), n>=1.
T(2n,2) = 2 + 5*A049684(n-1), n>=1.
T(2n+1,2) = 3 + 5*A058038(n-1), n>=1.
T(2n,3) = 3 + 5*A081016(n-2), n>=2.
T(2n+1,1) = 4 + 5*A003482(n-1), n>=1.
T(3n,1) = 4*A049629(n-1), n>=1.
T(3n,1) = 4 + 8*A119032(n), n>=1.
T(3n+1,3) = 8*A133273(n), n>=1.
T(3n+2,3n+2) = 2 + 32*A049664(n), n>=1.
T(3n,3n-2) = 4 + 32*A049664(n-1), n>=1.
T(3n+2,2) = 2 + 16*A049683(n), n>=1.
T(3n+2,2) = 2*A023039(n), n>=1.
T(2n-1,2n-1) = A033889(n-1), n>=1.
T(3n-1,3n-1) = 2*A007805(n-1), n>=1.
T(5n-1,1) = 11*A097842(n-1), n>=1.
T(4n+5,3) - T(4n+1,3) = 15*A000045(8n+1), n>=1.
T(5n+4,3) - T(5n-1,3) = 11*A000204(10n-2), n>=1.
Relations between left and right sides:
T(n,1) = T(n,n) - T(n-2,n-2), n>=3.
T(n,2) = T(n,n-1) - T(n-2,n-3), n>=4.
T(n,1) + T(n,n) = 3*T(n,n-1), n>=2.

A272099 Triangle read by rows, T(n,k) = C(n+1,k+1)*F([k-n, k-n-1], [-n-1], -1), where F is the generalized hypergeometric function, for n>=0 and 0<=k<=n.

Original entry on oeis.org

1, 4, 1, 12, 5, 1, 32, 18, 6, 1, 80, 56, 25, 7, 1, 192, 160, 88, 33, 8, 1, 448, 432, 280, 129, 42, 9, 1, 1024, 1120, 832, 450, 180, 52, 10, 1, 2304, 2816, 2352, 1452, 681, 242, 63, 11, 1, 5120, 6912, 6400, 4424, 2364, 985, 316, 75, 12, 1

Offset: 0

Peter Luschny, Apr 25 2016

This triangle results when the first column is removed from A210038. - Georg Fischer, Jul 26 2023

			Triangle starts:
1;
4,    1;
12,   5,    1;
32,   18,   6,   1;
80,   56,   25,  7,   1;
192,  160,  88,  33,  8,   1;
448,  432,  280, 129, 42,  9,  1;
1024, 1120, 832, 450, 180, 52, 10, 1;

A258109 (row sums), A008466 (alternating row sums), A001787 (col. 0), A001793 (col. 1), A055585 (col. 2).

Cf. A210038.

T := (n,k) -> binomial(n+1,k+1)*hypergeom([k-n, k-n-1], [-n-1], -1):
seq(seq(simplify(T(n,k)),k=0..n),n=0..9);

T[n_, k_] := Binomial[n+1, k+1] HypergeometricPFQ[{k-n, k-n-1}, {-n-1}, -1];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 22 2019 *)

cp's OEIS Frontend

A080936 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and height k (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A287213 Number T(n,k) of set partitions of [n] such that the maximal absolute difference between consecutive elements within a block equals k; triangle T(n,k), n>=0, 0<=k<=max(n-1,0), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A105693 a(n) = Fibonacci(2n+2)-2^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A276472 Modified Pascal's triangle read by rows: T(n,k) = T(n-1,k) + T(n-1,k-1), 12. T(n,n) = T(n,n-1) + T(n-1,n-1), n>1. T(1,1) = 1, T(2,1) = 1. n>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A272099 Triangle read by rows, T(n,k) = C(n+1,k+1)*F([k-n, k-n-1], [-n-1], -1), where F is the generalized hypergeometric function, for n>=0 and 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica