David Callan - cp's OEIS frontend

A351385 Triangle read by rows: T(n,k) = Sum_{j=k..n} binomial(n + j, n)*binomial(n, j)/(j + 1).

1, 2, 1, 6, 5, 2, 22, 21, 15, 5, 90, 89, 79, 49, 14, 394, 393, 378, 308, 168, 42, 1806, 1805, 1784, 1644, 1224, 594, 132, 8558, 8557, 8529, 8277, 7227, 4917, 2145, 429, 41586, 41585, 41549, 41129, 38819, 31889, 19877, 7865, 1430, 206098, 206097, 206052, 205392, 200772, 182754, 140712, 80652, 29172, 4862

Offset: 0

David Callan, Feb 09 2022

T(n,k) is the number of central Delannoy paths of steps E = (1,0), N = (0,1), D = (1,1) from the origin to (n,n) with k E steps above the diagonal line y=x. For example, T(3,1) = 5 counts ENNE, NEEN, NED, NDE, DNE. That the titular sum counts these paths is a consequence of the following equidistribution result: among the central Delannoy n-paths with j E steps, the statistic "number of E steps above y=x" is uniformly distributed over {0,1,...,j}. So, for k <= j <= n, there are binomial(n + j, n) binomial(n, j)/(j + 1) central Delannoy n-paths with j E steps, k of which are above y = x.

			Triangle begins:
   n
  [0]  1;
  [1]  2,  1;
  [2]  6,  5,  2;
  [3] 22, 21, 15,  5;
  [4] 90, 89, 79, 49, 14;
      ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Columns k=0..1 give: A006318, A035011.
Main diagonal gives A000108.
Row sums give A001850.
Cf. A001003, A002695, A080243, A088617 gives summands in title.

Flatten[Table[
  Sum[Binomial[n + j, n] Binomial[n, j]/(j + 1), {j, k, n}], {n, 0,
   10}, {k, 0, n}]]

T(n,k)={sum(j=k, n, binomial(n+j, n)*binomial(n,j)/(j+1))} \\ Andrew Howroyd, Feb 09 2022

G.f.: 2/(sqrt(1 - 6*x + x^2) + sqrt(1 - 2*x + x^2 - 4*x*y)).
From Alois P. Heinz, Feb 09 2022: (Start)
Sum_{k=0..n} k * T(n,k) = A002695(n).
Sum_{k=0..n} (-1)^k * T(n,k) = A001003(n).
Sum_{k=0..n} (-1)^k * T(n,n-k) = A080243(n). (End)

A350158 The distribution of the distance from the first weak subcedance to 1 on permutations.

Original entry on oeis.org

1, 2, 0, 5, 1, 0, 17, 5, 2, 0, 75, 23, 16, 6, 0, 407, 119, 104, 66, 24, 0, 2619, 719, 688, 558, 336, 120, 0, 19487, 5039, 4976, 4554, 3504, 2040, 720, 0, 164571, 40319, 40192, 38862, 34176, 25320, 14400, 5040, 0, 1555007, 362879, 362624, 358506, 338304, 287880, 207360, 115920, 40320, 0

Offset: 1

David Callan, Dec 17 2021

Triangular array read by rows. For 0 <= k <= n-1, T(n,k) is the number of permutations of [n] for which the difference between the position of 1 and the position of the first weak subcedance is k. A weak subcedance of a permutation pi is an entry pi(i) such that pi(i) <= i. See link.

			Triangle T(n,k) begins:
       1;
       2,     0;
       5,     1,     0;
      17,     5,     2,     0;
      75,    23,    16,     6,     0;
     407,   119,   104,    66,    24,     0;
    2619,   719,   688,   558,   336,   120,     0;
   19487,  5039,  4976,  4554,  3504,  2040,   720,    0;
  164571, 40319, 40192, 38862, 34176, 25320, 14400, 5040, 0;
  ...

David Callan, The distribution of the distance from the first weak subcedance to 1 on permutations

Cf. A129591 is the first column.

Row sums give A000142.

a[1, 0] = 1;
a[n_, 0] /; n >= 2 := 2 (n - 1)! + Sum[k^(n - k - 1) k!, {k, 1, n - 2}];
a[n_, k_] /; n > k >= 1 := (n - 1)! - k^(n - k - 1) k!;
Flatten[Table[a[n, k], {n, 10}, {k, 0, n - 1}]]

T(1,0) = 1, T(n,0) = 2*(n-1)! + Sum_{j=1..n-2} j^(n-j-1)*j! for n >= 2, T(n,k) = (n-1)! - k^(n-k-1)*k! for 1 <= k <= n-1.

A350114 Number of Deutsch paths with peaks at odd height.

Original entry on oeis.org

1, 0, 1, 0, 2, 2, 6, 11, 26, 56, 129, 294, 684, 1599, 3774, 8961, 21411, 51421, 124081, 300667, 731337, 1785010, 4370431, 10731270, 26419202, 65198847, 161262046, 399692001, 992559011, 2469265633, 6153306125, 15357906136, 38388056063, 96086525311, 240821963528

Offset: 0

David Callan, Dec 14 2021

a(n) is the number of closed Deutsch paths of n steps with all peaks at odd height. A Deutsch path is a lattice path of up-steps (1,1) and down-steps (1,-j), j>=1, starting at the origin that never goes below the x-axis, and it is closed if it ends on the x-axis.

A166300 counts closed Deutsch paths with all peaks at even height.

			a(5) = 2  counts UUU12, UUU21, where  U denotes an up-step and a down-step is denoted by its length, and a(6) = 6 counts UUUUU5, UUU1U3, UUU111, UUU3U1, U1UUU3, U1U1U1.

Helmut Prodinger, Deutsch paths and their enumeration, preprint, arXiv:2003.01918 [math.CO], 2020.

Cf. A166300.

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

With F = 1 + x^2 + 2*x^4 + 2*x^5+ ... the g.f. for Deutsch paths with all peaks at odd height and G = 1 + x^3 + x^4 + 2*x^5+ ... the g.f. for Deutsch paths with all peaks at even height, a count based on the decomposition of paths according to the size j of the first down-step (1,-j) that returns the path to ground level yields the pair of simultaneous equations
   F = 1 + (x^2*F*G + x^3*(F-1)*F*G)/(1 - x^2*F*G),
   G = 1 + (x^2*(F-1)*G  + x^3*F*G^2)/(1 - x^2*F*G).
G.f.:  (1 + x + x^2 - sqrt[(1 - 3*x + x^2)*(1 + x + x^2)])/(2*x*(1 + x)).
D-finite with recurrence (n+1)*a(n) +(-n+2)*a(n-1) +3*(-n+1)*a(n-2) +3*(-n+3)*a(n-3) +(-n+2)*a(n-4) +(n-5)*a(n-5)=0. - R. J. Mathar, Mar 06 2022

A346787 Ordered lone-child-avoiding trees where vertices have decreasing subtree sizes.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 68, 128, 253, 489, 981, 1930, 3899, 7771, 15858, 31915, 65503, 133070, 274631, 561371, 1164240, 2393652, 4983614, 10299238, 21511537, 44637483, 93552858, 194809152, 409270569, 855199845, 1800958182, 3773297872, 7963655481

Offset: 1

David Callan, Aug 03 2021

nonn

a(n) is the number of size-n, rooted, ordered, lone-child-avoiding trees in which the subtrees of each non-leaf vertex, taken left to right, have weakly decreasing sizes, where size is measured by number of vertices.

The analogous trees when size is measured by number of leaves are counted by A196545.

			See Link.

Alois P. Heinz, Table of n, a(n) for n = 1..2948
David Callan, Trees of size up to 7 for A346787
David Callan, A Combinatorial Interpretation for Sequence A345973 in OEIS, arXiv:2108.04969 [math.CO], 2021.

Cf. A196545.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
       b(n, i-1)+a(i)*b(n-i, min(n-i, i))))
    end:
a:= n-> b(n-1, n-2):
seq(a(n), n=1..40);  # Alois P. Heinz, Aug 05 2021

a[1] = 1; a[2] = 0;
a[n_] /; n >= 3 := a[n] = Apply[Plus, Map[Apply[Times, Map[a, #]] &, Rest[IntegerPartitions[n - 1]]]]
Table[a[n], {n, 20}]

Counting by sizes of subtrees of the root, a(n) is the sum, over all non-singleton partitions i_1,i_2,...,i_k of n-1, of the product a(i_1)a(i_2) ... a(i_k).

G.f. satisfies A(x)=x/((1+x)*Product_{n>=1} (1 - a(n)*x^n)).

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}]

A273821 Triangle read by rows: T(n,k) is the number of 123-avoiding permutations p of [n] (A000108) such that k is maximal with the property that the k largest entries of p, taken in order, avoid 132.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 0, 3, 3, 8, 0, 9, 10, 7, 16, 0, 28, 32, 25, 15, 32, 0, 90, 104, 84, 56, 31, 64, 0, 297, 345, 283, 195, 119, 63, 128, 0, 1001, 1166, 965, 676, 425, 246, 127, 256, 0, 3432, 4004, 3333, 2359, 1506, 894, 501, 255, 512

Offset: 1

David Callan, May 31 2016

It appears that each column, other than the first, has asymptotic growth rate of 4.

			For example, for the 123-avoiding permutation p = 42513, the 3 largest entries, 453, avoid 132 but the 4 largest entries, 4253, do not, and so p is counted by T(5,3).
Triangle begins:
1
0   2
0   1   4
0   3   3   8
0   9  10   7  16
0, 28, 32, 25, 15, 32
...

Except for the initial term, column 2 is A000245, column 3 is A071718, and row sums are A000108.

Map[Rest, Rest[Map[CoefficientList[#, y] &, CoefficientList[ Normal[Series[ c - 1 + ((1 - y) (1 - x y) (1 - (1 - x y) c ))/((1 - 2 x y) (1 - y + x y^2)) /. {c :> (1 - Sqrt[1 - 4 x])/(2 x)}, {x, 0, 10}, {y, 0, 10}]], x]]]]
u[1, 1] = 1; u[2, 2] = 2;
u[n_, 1] /; n > 1 := 0; u[n_, k_] /; n < 1 || k < 1 || k > n := 0;
u[n_, k_] /; n >= 3 && 2 <= k <= n := u[n, k] = 3 u[n - 1, k - 1] - 2 u[n - 2, k - 2] + u[n, k + 1] - 2 u[n - 1, k] + If[k == 2, CatalanNumber[n - 2], 0];
Table[u[n, k], {n, 10}, {k, n}]

G.f.: Sum_{n>=1, 1<=k<=n} T(n,k) x^n y^k = C(x) - 1 + ((1 - y) (1 - x y) (1 - (1 - x y)C(x)))/((1 - 2 x y) (1 - y + x y^2) ) where C(x) = 1 + x + 2x^2 + 5x^3 + ... is the g.f. for the Catalan numbers A000108 (conjectured).

A258041 Number of 312-avoiding derangements of {1,2,...,n}.

Original entry on oeis.org

1, 0, 1, 1, 4, 10, 31, 94, 303, 986, 3284, 11099, 38024, 131694, 460607, 1624451, 5771532, 20640334, 74246701, 268478962, 975436348, 3559204700, 13037907692, 47931423574, 176792821643, 654078238224, 2426705590840, 9026907769955

Offset: 0

David Callan, May 17 2015

nonn

In the Mathematica recurrence below, a(n,k) is the number of 312-avoiding permutations of {1,2,...,n} with no entry moved k places to the right of its "natural" position; thus a(n,0) = a(n). The recurrence for a(n,k) counts these permutations by the position j of 1 in the permutation.

Numerical evidence suggests lim_{n->inf} a(n)/a(n-1) = 4 and lim_{n->inf} A000108(n)/(n*a(n)) ~ .105.

			a(4) = 4 counts 2143, 2341, 3421, 4321.

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
Aaron Robertson, Dan Saracino, and Doron Zeilberger, Refined Restricted Permutations, arXiv:math/0203033 [math.CO], 2002.
Aaron Robertson, Dan Saracino, and Doron Zeilberger, Refined Restricted Permutations, Annals of Combinatorics 6 (2002) 427-444.

Cf. A000108, A000166, A061547.

a[n_, k_] /; k >= n := CatalanNumber[n]
a[n_, k_] /; 0 <= k < n :=
a[n, k] = Sum[a[j - 1, k + 1] a[n - j, k]  , {j, k}] + Sum[a[j - 1, k + 1] a[n - j, k],{j, k + 2, n}]
a[n_] := a[n, 0]
Table[a[n], {n, 0, 30}]

G.f.: 1/(1 + C(0)x -
         x/(1 + C(1)x^2 -
             x/(1 + C(2)x^3 -
                x/(1 + C(3)x^4 -
                   x/(1 + C(4)x^5 -
                      x/(1 + C(5)x^6 - ...)))))))) [continued fraction] where C(n) = A000108(n) is the n-th Catalan number.

A242136 Number of strong triangulations of a fixed square with n interior vertices.

Original entry on oeis.org

0, 1, 6, 36, 228, 1518, 10530, 75516, 556512, 4194801, 32224114, 251565996, 1991331720, 15953808780, 129171585690, 1055640440268, 8698890336576, 72215877581844, 603532770013080, 5074488683389840

Offset: 0

David Callan, Aug 15 2014

nonn

A strong triangulation is one in which no interior edge joins two vertices of the square (see W. G. Brown reference).

If the restriction "strong" is dropped, the counting sequence is A197271 (shifted left).

			The 6 triangulations for n=2 are as follows. Four have a central vertex joined to all 4 vertices of the square creating 4 triangular regions, one of which contains the second interior vertex. In these 4 cases, the central vertex has degree 5, the other interior  vertex has degree 3. In the other 2 triangulations, both interior vertices have degree 4, an opposite pair a, c of vertices of the square both have degree 3 (so 1 interior edge), and the other 2 opposite vertices have degree 4.

William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14, Issue 4, (1964) 746-768.
William T. Tutte, A census of planar triangulations (Eq. 5.12), Canad. J. Math. 14 (1962), 21-38.

Column k=1 of A341856.

Cf. A000260 for triangulations of a triangle.

A242136:=n->24*binomial(4*n+3,n-1)/((3*n+5)*(n+2)): seq(A242136(n), n=0..30); # Wesley Ivan Hurt, Aug 16 2014

Table[24 Binomial[4n+3,n-1]/((3n+5)(n+2)), {n, 0, 15}]

a(n) = 72 * (4*n+3)!/((3*n+6)!*(n-1)!) = 24 * binomial(4*n+3,n-1)/((3*n+5)*(n+2)) = binomial(4*n+3,n-1) - 5 * binomial(4*n+3,n-2) + 6 * binomial(4*n+3,n-3).

A219836 Triangular array counting derangements by number of descents.

Original entry on oeis.org

1, 2, 0, 4, 4, 1, 8, 24, 12, 0, 16, 104, 120, 24, 1, 32, 392, 896, 480, 54, 0, 64, 1368, 5544, 5984, 1764, 108, 1, 128, 4552, 30384, 57640, 34520, 6048, 224, 0, 256, 14680, 153400, 470504, 495320, 180416, 19936, 448, 1

Offset: 2

David Callan, Nov 29 2012

T(n,k) is the number of derangements of [n] with k descents.

			Array begins
1
2, 0
4, 4, 1
8, 24, 12, 0
16, 104, 120, 24, 1
T(4,2) = 4 counts 2143, 3142, 3421, 4312.

Shishuo Fu, Z. Lin, J. Zeng, Two new unimodal descent polynomials, arXiv preprint arXiv:1507.05184 [math.CO], 2015-2019.

Cf. A008292. (analogous for permutations)

Row sums give A000166. A046739 counts derangements of [n] by number of excedances.

u[n_, 0] := 0; u[n_, k_] /; k == n-1 := If [EvenQ[n], 1, 0]; u[n_, k_] /; 1 <= k <= n - 2 := (n - k) u[n - 1, k - 1] + (k + 1) u[n - 1, k]; Table[u[n, k], {n, 2, 10}, {k, n - 1}]

The g.f. F(x,y) = Sum_{n>=2,1<=k<=n-1}T(n,k)x^n/n!y^k satisfies the partial differential equation (1-xy) D_{x}F + (y^2-y) D_{y}F = F + 1 - e^(-xy). (Is there a closed form solution?)

A217922 Triangle read by rows: labeled trees counted by improper edges.

Original entry on oeis.org

1, 1, 2, 1, 6, 7, 3, 24, 46, 40, 15, 120, 326, 430, 315, 105, 720, 2556, 4536, 4900, 3150, 945, 5040, 22212, 49644, 70588, 66150, 38115, 10395, 40320, 212976, 574848, 1011500, 1235080, 1032570, 540540, 135135

Offset: 1

David Callan, Oct 14 2012

T(n,k) is the number of labeled trees on [n], rooted at 1, with k improper edges, for n >= 1, k >= 0. See Zeng link for definition of improper edge.

			Triangle begins:
  \ k  0....1....2....3....4......
  n
  1 |..1
  2 |..1
  3 |..2....1
  4 |..6....7....3
  5 |.24...46...40....15
  6 |120..326..430...315...105
T(4,2) = 3 because we have 1->3->4->2, 1->4->2->3, 1->4->3->2, in each of which the last 2 edges are improper.

G. C. Greubel, Rows n = 1..50 of the irregular triangle, flattened
J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013-2014.
William Y. C. Chen, Amy M. Fu, and Elena L. Wang, A Grammatical Calculus for the Ramanujan Polynomials, arXiv:2506.01649 [math.CO], 2025. See p. 3.
Dominique Dumont and Armand Ramamonjisoa, Grammaire de Ramanujan et Arbres de Cayley, Electr. J. Combinatorics, Volume 3, Issue 2 (1996) R17 (see page 17).
Matthieu Josuat-Vergès, Derivatives of the tree function, arXiv preprint arXiv:1310.7531 [math.CO], 2013.
Lucas Randazzo, Arboretum for a generalization of Ramanujan polynomials, arXiv:1905.02083 [math.CO], 2019.
Jiang Zeng, A Ramanujan sequence that refines the Cayley formula for trees, Ramanujan Journal 3 (1999) 1, 45-54, [DOI]

Row sums are A000272.

Cf. A054589, A075856.

function T(n,k) // T = A217922
  if k lt 0 or k gt n-2 then return 0;
  elif k eq 0 then return Factorial(n-1);
  else return (n-1)*T(n-1,k) + (n+k-3)*T(n-1,k-1);
  end if;
end function;
[1] cat [T(n,k): k in [0..n-2], n in [2..12]]; // G. C. Greubel, Jan 10 2025

T[n_, k_]:= T[n,k]= If[k<0 || k>n-2, 0, If[k==0, (n-1)!, (n-1)*T[n-1,k] + (n+k-3)*T[n-1, k-1]]];
Join[{1}, Table[T[n,k], {n,12}, {k,0,n-2}]//Flatten] (* modified by G. C. Greubel, May 07 2019 *)

def T(n, k):
    if k==0: return factorial(n-1)
    elif (k<0 or k > n-2): return 0
    else: return (n-1)*T(n-1, k) + (n+k-3)* T(n-1, k-1)
flatten([1] + [[T(n, k) for k in (0..n-2)] for n in (2..12)]) # G. C. Greubel, May 07 2019

T(n, k) = (n-1)*T(n-1, k) + (n+k-3)*T(n-1, k-1), for 1 <= k <= n-2, with T(n, 0) = (n-1)!. - G. C. Greubel, Jan 10 2025

cp's OEIS Frontend

User: David Callan

A351385 Triangle read by rows: T(n,k) = Sum_{j=k..n} binomial(n + j, n)*binomial(n, j)/(j + 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A350158 The distribution of the distance from the first weak subcedance to 1 on permutations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A350114 Number of Deutsch paths with peaks at odd height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A346787 Ordered lone-child-avoiding trees where vertices have decreasing subtree sizes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A273821 Triangle read by rows: T(n,k) is the number of 123-avoiding permutations p of [n] (A000108) such that k is maximal with the property that the k largest entries of p, taken in order, avoid 132.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A258041 Number of 312-avoiding derangements of {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A242136 Number of strong triangulations of a fixed square with n interior vertices.