A035929 -id:A035929 - cp's OEIS frontend

A114589 Number of hill-free Dyck paths of semilength n+3 and having no peaks at even levels (a hill in a Dyck path is a peak at level 1).

1, 1, 3, 7, 17, 43, 110, 286, 753, 2003, 5376, 14540, 39589, 108427, 298512, 825664, 2293271, 6393539, 17885835, 50191175, 141247519, 398537101, 1127203038, 3195229662, 9076078057, 25830193513, 73643406563, 210312889095

Offset: 0

Emeric Deutsch, Dec 11 2005

nonn

Column 0 of A114588. The number of hill-free Dyck paths having no peaks at odd level are given by the Riordan numbers (A005043).
From Paul Barry, Jul 05 2009: (Start)
The sequence 1,0,0,1,1,3,7,...
has g.f. ((1+x)*(1+2*x)-sqrt((1+x)*(1-3*x)))/(2*x*(2+2*x+x^2)).
It is the inverse binomial transform of A035929(n+1). (End)

			a(2)=3 because we have UUUDDUUDDD, UUUDUDUDDD and UUUUUDDDDD, where U=(1,1), D=(1,-1).

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A114588, A005043.

G:=(1-z-2*z^2-2*z^3-sqrt(1-3*z^2-2*z))/2/z^4/(2+2*z+z^2): Gser:=series(G,z=0,35): 1, seq(coeff(Gser,z^n),n=1..30);

CoefficientList[Series[(1-x-2*x^2-2*x^3-Sqrt[1-3*x^2-2*x])/2/x^4 /(2+2*x+x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)

x='x+('x^50); Vec((1-x-2*x^2-2*x^3-sqrt(1-3*x^2-2*x))/(2*x^4*(2+2*x+x^2))) \\ G. C. Greubel, Mar 17 2017

G.f.: (1 -z -2*z^2 -2*z^3 -sqrt(1-3*z^2-2*z))/(2*z^4*(2+2*z+z^2)).
a(n) ~ 3^(n+11/2) / (50*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 20 2014
Conjecture: 2*(n+4)*a(n) +2*(-n-1)*a(n-1) +3*(-3*n-4)*a(n-2) +(-8*n-11)*a(n-3) +3*(-n-1)*a(n-4)=0. - R. J. Mathar, Jul 02 2018

A165543 Number of permutations of length n which avoid both the patterns 3241 and 4321. Or, equivalently, avoids both 1234 and 1342.

Original entry on oeis.org

1, 1, 2, 6, 22, 89, 380, 1678, 7584, 34875, 162560, 766124, 3644066, 17469863, 84324840, 409471090, 1998933556, 9804748548, 48298256084, 238840150970, 1185256302910, 5900843531665, 29464355189120, 147522603762870, 740471407808372, 3725334547101464, 18782663124890072, 94889671255981134

Offset: 0

Vincent Vatter, Sep 21 2009

nonn

These permutations have an enumeration scheme of depth 4.

Conjecturally, a(n) is the number of permutations pi of length n such that s(pi) avoids the patterns 231 and 321, where s denotes West's stack-sorting map. - Colin Defant, Sep 17 2018

			There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

Christian Bean, Combinatorial Exploration and Permutation Classes, talk in RUTGERS Experimental Mathematics Seminar Series, Thursday, March 27, 2025, (https://sites.math.rutgers.edu/~zeilberg/expmath/). The last slide is devoted to this sequence - N. J. A. Sloane, Apr 06 2025

Vincenzo Librandi, Table of n, a(n) for n = 0..270
J. Bloom and V. Vatter, Two Vignettes On Full Rook Placements, arXiv preprint arXiv:1310.6073 [math.CO], 2013.
J. Bloom and V. Vatter, Two Vignettes On Full Rook Placements, The Australasian Journal of Combinatorics, vol. 64(1), 2016, p. 80.
David Callan, Permutations avoiding 4321 and 3241 have an algebraic generating function, arXiv:1306.3193 [math.CO], 2013.
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
Darla Kremer and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
Toufik Mansour, Howard Skogman, and Rebecca Smith, Passing through a stack k times with reversals, arXiv:1808.04199 [math.CO], 2018.
Permutation Pattern Avoidance Library (PermPAL), Av(1234,1342).
V. Vatter, Enumeration schemes for restricted permutations, Combin., Prob. and Comput. 17 (2008), 137-159.
Wikipedia, Permutation classes avoiding two patterns of length 4.

a[0] = 1; a[n_] := Sum[ (m*Sum[ (k*Binomial[m+2*k-1, m+k-1]*Binomial[2*(n-m)-k-1, n-m-1])/(m + k), {k, 1, n-m}])/(n-m), {m, 1, n-1}] + 1; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Jun 25 2013 *) (* adapted by Vincenzo Librandi, May 14 2017 *)

a(n):=if n=0 then 0 else sum((m*sum((k*binomial(m+2*k-1,m+k-1)*binomial(2*(n-m)-k-1,n-m-1))/(m+k),k,1,n-m))/(n-m),m,1,n-1)+1; /* Vladimir Kruchinin, May 12 2011 */

From Vladimir Kruchinin, May 12 2011: (Start)
G.f.: 1/(1-x*A000108(x*A000108(x)))
a(n) = sum(m=1..n-1, (m*sum(k=1..n-m, (k*binomial(m+2*k-1,m+k-1)*binomial(2*(n-m)-k-1,n-m-1))/(m+k)))/(n-m))+1. (End)
From Gary W. Adamson, Nov 14 2011: (Start)
a(n) is the top left term in M^n, M = an infinite square production matrix with A000108 as the left column, as follows:
  1, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  2, 1, 1, 1, 0, ...
  5, 1, 1, 1, 1, ...
  ... (End)
G.f.: A035929(x)/x composed with x*A000108(x). - Alexander Burstein, Aug 07 2017
a(n) ~ 2^(4*n + 3/2) / (25 * sqrt(Pi) * n^(3/2) * 3^(n - 3/2)). - Vaclav Kotesovec, Aug 14 2018

a(0)=1 prepended by Alois P. Heinz, Feb 18 2016

Definition expanded by N. J. A. Sloane, Apr 28 2025

A182486 Expansion of 2 * (2 + x) / (4 - x - x * sqrt(1 - 4*x)) in powers of x.

Original entry on oeis.org

1, 1, 0, -1, -2, -4, -10, -29, -90, -290, -960, -3246, -11164, -38934, -137358, -489341, -1757882, -6360634, -23160528, -84802606, -312041692, -1153271984, -4279311348, -15935808866, -59537435012, -223099337404, -838282693560, -3157706225584, -11922241414880

Offset: 0

Michael Somos, May 02 2012

sign

HANKEL transform of sequence and the sequence omitting a(0) is the sequence A033999(n) = (-1)^n. This is the unique sequence with that property.

			G.f. = 1 + x - x^3 - 2*x^4 - 4*x^5 - 10*x^6 - 29*x^7 - 90*x^8 - 290*x^9 + ...
1 = det([ 1]) = det([ 1]). -1 = det([ 1, 1; 1, 0]) = det([ 1, 0; 0, -1]). 1 = det([ 1, 1, 0; 1, 0, -1; 0, -1, -2]) = det([ 1, 0, -1; 0, -1, -2; -2, -4, -10]).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.

Cf. A033999, A035929, A135334.

m:=25; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!(2*(2+x)/(4-x -x*Sqrt(1-4*x)))); // G. C. Greubel, Aug 11 2018

CoefficientList[Series[2*(2+x)/(4-x -x*Sqrt[1-4*x]), {x, 0, 50}], x] (* G. C. Greubel, Aug 11 2018 *)

{a(n) = if( n<0, 0, polcoeff( 2 * (2 + x) / (4 - x - x * sqrt(1 - 4*x + x * O(x^n))) ,n))}

{a(n) = if( n<1, n==0, polcoeff( subst( (1 + x) / (1 + x^2), x, serreverse( x - x^2 + x * O(x^n))), n))}

G.f.: 2 * (2 + x) / (4 - x - x * sqrt(1 - 4*x)).
G.f.: (4 - x + x * sqrt(1 - 4*x)) / (2 * (2 - 2*x + x^2)).
G.f.: 1 / (1 - x / (1 + x / (1 - x / (1 - x / (1 - x / ...))))).
a(n) = -A135334(n - 2) if n > 2. a(n) - a(n+1) = A035929(n).
D-finite with recurrence: 2*(-n+1)*a(n) +2*(5*n-11)*a(n-1) +3*(-3*n+7)*a(n-2) +2*(2*n-5)*a(n-3)=0. - R. J. Mathar, Jun 08 2016

cp's OEIS Frontend

A114589 Number of hill-free Dyck paths of semilength n+3 and having no peaks at even levels (a hill in a Dyck path is a peak at level 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A165543 Number of permutations of length n which avoid both the patterns 3241 and 4321. Or, equivalently, avoids both 1234 and 1342.

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Mathematica

Maxima

Formula

Extensions

A182486 Expansion of 2 * (2 + x) / (4 - x - x * sqrt(1 - 4*x)) in powers of x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula