A126182 -id:A126182 - cp's OEIS frontend

A026378 a(n) = number of integer strings s(0),...,s(n) counted by array T in A026374 that have s(n)=1; also a(n) = T(2n-1,n-1).

1, 4, 17, 75, 339, 1558, 7247, 34016, 160795, 764388, 3650571, 17501619, 84179877, 406020930, 1963073865, 9511333155, 46169418195, 224484046660, 1093097083475, 5329784874185, 26018549129545, 127154354598330, 622031993807565

Offset: 1

Clark Kimberling

nonn

Number of lattice paths from (0,0) to the line x=n-1 that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and three types of steps H=(1,0) (left factors of 3-Motzkin steps). Example: a(3)=17 because we have UD, UU, 9 HH paths, 3 HU paths and 3 UH paths. - Emeric Deutsch, Jan 22 2004
Also a(n) = number of integer strings s(0), ..., s(n) counted by array U in A026386 that have s(n)=1; a(n) = U(2n-1, n-1).
The Hankel transform of [1,1,4,17,75,339,1558,...] is [1,3,8,21,55,144,377,...] (see A001906). - Philippe Deléham, Apr 13 2007
Number of peaks in all skew Dyck paths of semilength n. A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps. Example: a(2)=4 because in the 3 (=A002212(2)) skew Dyck paths (UD)(UD), U(UD)D and U(UD)L we have altogether 4 peaks (shown between parentheses). - Emeric Deutsch, Jul 25 2007
Hankel transform of this sequence gives A000012 = [1,1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
5th binomial transform of (-1)^n*A000108. - Paul Barry, Jan 13 2009
From Gary W. Adamson, May 17 2009: (Start)
Convolved with A007317, (1, 2, 5, 15, 51, ...) = A026376: (1, 6, 30, 144, ...)
Equals A026375, (1, 3, 11, 45, 195, ...) convolved with A002212 prefaced with
a 1: (1, 1, 3, 10, 36, 137, ...). (End)
From Tom Copeland, Nov 09 2014: (Start)
The array belongs to an interpolated family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the interpolating o.g.f. [1-sqrt(1-4x/(1+(1-t)x))]/2 and inverse x(1-x)/[1+(t-1)x(1-x)]. See A091867 for more info on this family. Here the interpolation is t=-4 (mod signs in the results).
Let C(x) = [1 - sqrt(1-4x)]/2, an o.g.f. for the Catalan numbers A000108, with inverse Cinv(x) = x*(1-x) and P(x,t) = x/(1+t*x) with inverse P(x,-t).
O.g.f: G(x) = [-1 + sqrt(1 + 4*x/(1-5x))]/2 = -C[P(-x,5)].
Inverse O.g.f: Ginv(x) = x*(1+x)/[1 + 5x*(1+x)] = -P(Cinv(-x),-5) (signed A039717). (End)

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Shu-Chiuan Chang, Robert Shrock, Structure of the Partition Function and Transfer Matrices for the Potts Model in a Magnetic Field on Lattice Strips, J. Stat. Physics 137 (2009) 667, table 5.
D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
Isaac DeJager, Madeleine Naquin, Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Toufik Mansour, Jose Luis Ramirez, Enumration of Fuss-skew paths, Ann. Math. Inform. 55 (2022) 125-136, table 2, l=1.
László Németh, Tetrahedron trinomial coefficient transform, arXiv:1905.13475 [math.CO], 2019.

Half the values of A026387. Bisection of A026380 and A026392.
Cf. A026375, A026376, A007317, A002212. - Gary W. Adamson, May 17 2009
Cf. A000108, A005043, A026375, A026380, A039717, A091867, A126182.

a := n -> (-1)^n*simplify(GegenbauerC(n-2,-n+1,3/2) - GegenbauerC(n-1,-n+1,3/2)): seq(a(n), n=1..23); # Peter Luschny, May 13 2016

CoefficientList[Series[(1/2)/(5*x^2-x)*(1-5*x-(1-6*x+5*x^2)^(1/2)),{x,0,30}],x] (* Vincenzo Librandi, May 13 2012 *)
Table[Hypergeometric2F1[3/2, 1-n, 2, -4], {n, 1, 20}] (* Vladimir Reshetnikov, Apr 25 2016 *)

G.f.: (1/2)/(5*x^2-x)*(1-5*x-(1-6*x+5*x^2)^(1/2)). E.g.f.: exp(3*x)*(BesselI(0, 2*x)+BesselI(1, 2*x)). - Vladeta Jovovic, Oct 03 2003
G.f.: [(1-z)/sqrt(1-6z+5z^2)-1]/2 = z + 4z^2 + 17z^3 + ... - Emeric Deutsch, Jan 22 2004
a(n) = coefficient of t^n in (1+t)(1+3t+t^2)^(n-1). - Emeric Deutsch, Jan 30 2004
a(n) = A026380(2n-2). - Emeric Deutsch, Feb 18 2004
a(n) = [2(3n-2)a(n-1) - 5(n-2)a(n-2)]/n for n>=2; a(0)=0, a(1)=1. - Emeric Deutsch, Mar 18 2004
a(n+1) = sum(k=0, n, binomial(n, k)*sum(i=0, k, binomial(k+i, i))). - Benoit Cloitre, Aug 06 2004
a(n+1) = sum(k=0, n, binomial(n, k)*binomial(2*k+1, k+1)). - Benoit Cloitre, Aug 06 2004
a(n) = Sum(k*A126182(n-1,k-1),k=1..n). - Emeric Deutsch, Jul 25 2007
From Paul Barry, Jan 13 2009: (Start)
G.f.: (1/(1-5x))*c(-x/(1-5x)), c(x) the g.f. of A000108;
a(n) = sum{k=0..n, C(n,k)*(-1)^k*A000108(k)*5^(n-k)} (offset 0). (End)
G.f. 1/(1 - 3x - x(1 - x)/(1 - x - x(1 - x)/(1 - x - x(1 - x)/(1 - x - x(1 - x)/(1...(continued fraction). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Jul 02 2010
a(n) ~ 5^(n-1/2)/sqrt(Pi*n). - Vaclav Kotesovec, Oct 08 2012
a(n) = hypergeom([3/2, 1-n], [2], -4). - Vladimir Reshetnikov, Apr 25 2016
a(n) = (-1)^n*(GegenbauerC(n-2,-n+1,3/2) - GegenbauerC(n-1,-n+1,3/2)). - Peter Luschny, May 13 2016

A126216 Triangle read by rows: T(n,k) is the number of Schroeder paths of semilength n containing exactly k peaks but no peaks at level one (n >= 1; 0 <= k <= n-1).

Original entry on oeis.org

1, 2, 1, 5, 5, 1, 14, 21, 9, 1, 42, 84, 56, 14, 1, 132, 330, 300, 120, 20, 1, 429, 1287, 1485, 825, 225, 27, 1, 1430, 5005, 7007, 5005, 1925, 385, 35, 1, 4862, 19448, 32032, 28028, 14014, 4004, 616, 44, 1, 16796, 75582, 143208, 148512, 91728, 34398, 7644, 936, 54, 1

Offset: 1

Emeric Deutsch, Dec 20 2006

A Schroeder path of semilength n is a lattice path in the first quadrant, from the origin to the point (2n,0) and consisting of steps U=(1,1), D=(1,-1) and H=(2,0).
Also number of Schroeder paths of semilength n containing exactly k doublerises but no (2,0) steps at level 0 (n >= 1; 0 <= k <= n-1). Also number of doublerise-bicolored Dyck paths (doublerises come in two colors; also called marked Dyck paths) of semilength n and having k doublerises of a given color (n >= 1; 0 <= k <= n-1). Also number of 12312- and 121323-avoiding matchings on [2n] with exactly k crossings.
Essentially the triangle given by [1,1,1,1,1,1,1,1,...] DELTA [0,1,0,1,0,1,0,1,0,1,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 20 2007
Mirror image of triangle A033282. - Philippe Deléham, Oct 20 2007
For relation to Lagrange inversion, or series reversion and the geometry of associahedra, or Stasheff polytopes (and other combinatorial objects), see A133437. - Tom Copeland, Sep 29 2008
First column (k=0) gives the Catalan numbers (A000108). - Alexander Karpov, Jun 10 2018
T(n,k) is the multiplicity of the k-hook representation of the symmetric group in the (n-1)st parking space representation (see Pak and Postnikov, 1995). - Joshua Mundinger, Jul 18 2025

			T(3,1)=5 because we have HUUDD, UUDDH, UUUDDD, UHUDD and UUDHD.
Triangle starts:
   n\k  0      1      2      3      4     5    6   7  8
   1    1;
   2    2,     1;
   3    5,     5;     1;
   4   14,    21,     9,     1;
   5   42,    84,    56,    14,     1;
   6  132,   330,   300,   120,    20,    1;
   7  429,  1287,  1485,   825,   225,   27,   1;
   8 1430,  5005,  7007,  5005,  1925,  385,  35,  1;
   9 4862, 19448, 32032, 28028, 14014, 4004, 616, 44, 1;
  10 ...
Triangle [1,1,1,1,1,1,1,...] DELTA [0,1,0,1,0,1,0,1,...] begins:
   1;
   1,  0;
   2,  1,  0;
   5,  5,  1,  0;
  14, 21,  9,  1,  0;
  42, 84, 56, 14,  1,  0;
  ...

Gheorghe Coserea, Rows n = 1..200, flattened
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns, The Electronic Journal of Combinatorics 13, 2006, #R112, Theorem 3.3.
D. Callan, Polygon Dissections and Marked Dyck Paths
Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms, 2015.
D. Drake, Bijections from Weighted Dyck Paths to Schröder Paths, J. Int. Seq. 13 (2010) #10.9.2.
Rosena R. X. Du, Xiaojie Fan, and Yue Zhao, Enumeration on row-increasing tableaux of shape 2 X n, arXiv:1803.01590 [math.CO], 2018.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
S. Mizera, Combinatorics and Topology of Kawai-Lewellen-Tye Relations, arXiv:1706.08527 [hep-th], 2017.
Jean-Christophe Novelli and Jean-Yves Thibon, Duplicial algebras and Lagrange inversion, arXiv preprint arXiv:1209.5959 [math.CO], 2012.
Jean-Christophe Novelli and Jean-Yves Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014. See Fig. 7.
I. Pak and A. Postnikov, Enumeration of trees and one amazing representation of the symmetric group, Proceedings of the 8-th International Conference FPSAC, 1996.

Cf. A000108, A002054, A002055, A002056, A007160, A033280, A033281, A033282.
Cf. A126182.
Cf. A086810, A126120, A243660, A243661.

T:=(n,k)->binomial(n,k)*binomial(2*n-k,n+1)/n: for n from 1 to 11 do seq(T(n,k),k=0..n-1) od; # yields sequence in triangular form

Table[Binomial[n, k] Binomial[2 n - k, n + 1]/n, {n, 10}, {k, 0, n - 1}] // Flatten (* Michael De Vlieger, Jan 09 2016 *)

tabl(nn) = {mP = matrix(nn, nn, n, k, binomial(n-1, k-1)); mN = matrix(nn, nn, n, k, binomial(n-1, k-1) * binomial(n, k-1) / k); mprod = mN*mP; for (n=1, nn, for (k=1, n, print1(mprod[n, k], ", ");); print(););} \\ Michel Marcus, Apr 16 2015

t(n,k) = binomial(n,k)*binomial(2*n-k,n+1)/n;
concat(vector(10, n, vector(n, k, t(n,k-1))))  \\ Gheorghe Coserea, Apr 24 2016

T(n,k) = C(n,k)*C(2*n-k,n+1)/n (0 <= k <= n-1).
G.f.: G(t,z) = (1-2*z-t*z-sqrt(1-4*z-2*t*z+t^2*z^2))/(2*(1+t)*z).
Equals N * P, where N = the Narayana triangle (A001263) and P = Pascal's triangle, as infinite lower triangular matrices. A126182 = P * N. - Gary W. Adamson, Nov 30 2007
G.f.: 1/(1-x-(x+xy)/(1-xy/(1-(x+xy)/(1-xy/(1-(x+xy)/(1-xy/(1-.... (continued fraction). - Paul Barry, Feb 06 2009
Let h(t) = (1-t)^2/(1+(u-1)*(1-t)^2) = 1/(u + 2*t + 3*t^2 + 4*t^3 + ...), then a signed (n-1)-th row polynomial of A126216 is given by u^(2n-1)*(1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=2. The power series expansion of h(t) is related to A181289 (cf. A086810). - Tom Copeland, Oct 09 2011
From Tom Copeland, Oct 10 2011: (Start)
With polynomials
P(0,t) = 0
P(1,t) = 1
P(2,t) = 1
P(3,t) = 2 + t
P(4,t) = 5 + 5 t + t^2
P(5,t) = 14 + 21 t + 9 t^2 + t^3
The o.g.f. A(x,t) = (1+x*t-sqrt((1-x*t)^2-4x))/(2(1+t)), and
B(x,t) = x - x^2/(1-t*x) = x - x^2 - ((t*x)^3 + (t*x)^4 + ...)/t^2 is the compositional inverse in x. [series corrected by Tom Copeland, Dec 10 2019]
Let h(x,t) = 1/(dB/dx) = (1-tx)^2/(1-(t+1)(2x-tx^2)) = 1/(1 - 2x - 3tx^2 + 4t^2x^3 + ...). Then P(n,t) = (1/n!)(h(x,t)*d/dx)^n x, evaluated at x=0, A = exp(x*h(u,t)*d/du) u, evaluated at u=0, and dA/dx = h(A(x,t),t). (End)
From Tom Copeland, Dec 09 2019: (Start)
The polynomials in my 2011 formula entry above evaluate to an aerated, alternating sign sequence of the Catalan numbers A000108 with t = -2. The first few are P(2,-2) = 1, P(3,-2) = 0, P(4,t) = -1, P(5,-2) = 0, P(6,-2) = 2, P(7,-2) = 0, P(8,-2) = -5, P(9,-2) = 0, P(10,-2) = 14.
Generalizing the relations between w = theta and u = phi in Mizera on pp. 32-34, modify the inverse pair above to w = i * B(-i*u,t) = u + i * u^2/(1+i*t*u), where i is the imaginary number, and u = i*A(-i*w,t) = i*(1 - i*w*t - sqrt((1 + i*w*t)^2 + i*4*w))/(2(1+t)). Then the expression for V'(w) in Mizera generalizes to V'(w) = -i*(w - u) and reduces to V'(w) = (1 - sqrt(1-4 w^2))/2 when evaluated at t = -2, which is an o.g.f. for A126120. Cf. also A086810. (End)
Sum_{k = 0..n-1} (-1)^k*T(n,k)*binomial(x + 2*n - k, 2*n - k) = ( (x + 1) * ( Product_{k = 2..n} (x + k)^2 ) * (x + n + 1) )/(n!*(n + 1)!) for n >= 1. Cf. A243660 and A243661. - Peter Bala, Oct 08 2022

A128718 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k UU's (doublerises) (n >= 1; 0 <= k <= n-1).

Original entry on oeis.org

1, 1, 2, 1, 5, 4, 1, 9, 18, 8, 1, 14, 50, 56, 16, 1, 20, 110, 220, 160, 32, 1, 27, 210, 645, 840, 432, 64, 1, 35, 364, 1575, 3150, 2912, 1120, 128, 1, 44, 588, 3388, 9534, 13552, 9408, 2816, 256, 1, 54, 900, 6636, 24822, 49644, 53088, 28800, 6912, 512, 1, 65, 1320, 12090, 57750, 153426, 231000, 193440, 84480, 16640, 1024

Offset: 1

Emeric Deutsch, Mar 30 2007

A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of its steps.

Row sums yield A002212.

			T(3,2)=4 because we have UUUDDD, UUUDLD, UUUDDL and UUUDLL.
Triangle starts:
  1;
  1,  2;
  1,  5,  4;
  1,  9, 18,  8;
  1, 14, 50, 56, 16;

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.

Cf. A000096, A002212, A126182, A128743.

T:=proc(n,k) if k=0 then 1 else binomial(n,k)*sum(binomial(k,j)*binomial(n-k+j,j+1),j=0..k)/n fi end: for n from 1 to 11 do seq(T(n,k),k=0..n-1) od; # yields sequence in triangular form

m = 12; G[_] = 0;
Do[G[z_] = 1 + t z G[z]^2 + z G[z] - t z + O[z]^m, {m}];
CoefficientList[#, t]& /@ CoefficientList[G[z], z] // Rest // Flatten (* Jean-François Alcover, Nov 15 2019 *)

T(n,0) = 1;
T(n,1) = (n-1)(n+2)/2 = A000096(n-1);
T(n,k) = A126182(n,n-k), i.e., triangle is mirror image of A126182.
Sum_{k=0..n-1} k*T(n,k) = A128743(n).
T(n,k) = (binomial(n,k)/n)*Sum_{j=0..k} binomial(k,j)*binomial(n-k+j, j+1) (1 <= k <= n).
G.f.: G - 1, where G = G(t,z) satisfies G = 1 + tzG^2 + zG - tz.

A128747 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k peaks of height >1 (n >= 1; 0 <= k <= n-1).

Original entry on oeis.org

1, 1, 2, 1, 7, 2, 1, 18, 15, 2, 1, 41, 68, 25, 2, 1, 88, 244, 171, 37, 2, 1, 183, 765, 866, 351, 51, 2, 1, 374, 2199, 3651, 2355, 636, 67, 2, 1, 757, 5954, 13601, 12708, 5421, 1058, 85, 2, 1, 1524, 15438, 46355, 58977, 36198, 11116, 1653, 105, 2, 1, 3059, 38747, 147768

Offset: 1

Emeric Deutsch, Mar 31 2007

Row sums yield A002212.

			T(3,1)=7 because we have UDU(UD)D, UDU(UD)L, U(UD)DUD, UU(UD)DD, UU(UD)LD, UU(UD)DL and UU(UD)LL (the peaks of height >1 are shown between parentheses).
Triangle starts:
  1;
  1,  2;
  1,  7,  2;
  1, 18, 15,  2;
  1, 41, 68, 25,  2;

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.

Cf. A002212, A128748.

K:=(1-z*t-sqrt(z^2*t^2-2*z*t+1+4*z^2-4*z))/2/z: G:=z*(2*K-1)/(1-z*K): Gser:=simplify(series(G,z=0,14)): for n from 1 to 11 do P[n]:=sort(coeff(Gser,z,n)) od: for n from 1 to 11 do seq(coeff(P[n],t,j),j=0..n-1) od; # yields sequence in triangular form

T(n,0) = 1.
Sum_{k=0..n-1} k*T(n,k) = A128748(n).
G.f.: G(t,z) = (1 - z + z*K(t,z))/(1 - z*K(t,z)) - 1, where K = K(t,z) satisfies zK^2 - (1 - tz)K + 1 - z = 0 (K is the g.f. for the number of peaks; see A126182).

cp's OEIS Frontend

A026378 a(n) = number of integer strings s(0),...,s(n) counted by array T in A026374 that have s(n)=1; also a(n) = T(2n-1,n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A126216 Triangle read by rows: T(n,k) is the number of Schroeder paths of semilength n containing exactly k peaks but no peaks at level one (n >= 1; 0 <= k <= n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A128718 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k UU's (doublerises) (n >= 1; 0 <= k <= n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A128747 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k peaks of height >1 (n >= 1; 0 <= k <= n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula