A098746 Number of permutations of [1..n] which avoid 4231 and 42513.

1, 1, 2, 6, 23, 102, 495, 2549, 13682, 75714, 428882, 2474573, 14492346, 85926361, 514763279, 3111119358, 18946375767, 116147683902, 716179441293, 4438862153246, 27638747494178, 172805469880497, 1084462349973559, 6828717036765622, 43132158190994223, 273204023401012901

Offset: 0

Author

N. J. A. Sloane, Oct 30 2004

Keywords

• nonn
• easy

Comments

(a(n)){n>=1} is the INVERT transform of (u(n)){n>=1}:=(1,1,3,12,55,273,...), the ternary numbers A001764. - David Callan, Nov 21 2011

a(n) = number of Dyck paths of semilength 2n for which all descents are of even length (counted by A001764) with no valley vertices at height 1. For example, a(2)=2 counts UUUUDDDD, UUDDUUDD. - David Callan, Nov 21 2011

Conjecture: a(n) is the number of permutations of [1..n] which avoid 1342 and 13254. - Alexander Burstein, Oct 19 2017

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• M. H. Albert et al., Restricted permutations and queue jumping, Discrete Math., 287 (2004), 129-133.
• Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.
• Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
• Wlodzimierz Bryc, Raouf Fakhfakh, and Wojciech Mlotkowski, Cauchy-Stieltjes families with polynomial variance functions and generalized orthogonality, arXiv:1708.05343 [math.PR], 2017-2019. Also in Probability and Mathematical Statistics (2019), Vol. 39, No. 2, 237-258.
• Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy.
• Joanna N. Chen and Zhicong Lin, Combinatorics of the symmetries of ascents in restricted inversion sequences, arXiv:2112.04115 [math.CO], 2021.
• Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
• Toufik Mansour and Mark Shattuck, Further enumeration results concerning a recent equivalence of restricted inversion sequences, hal-03295362 [math.CO], 2021.
• Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016 [Section 2.26].

Crossrefs

Cf. A000108, A001764.

Programs

Maple

1+add( t^n * add( (n-l)*binomial(2*l+n,l)/(2*l+n), l=0..n ), n=1..30);

Mathematica

Flatten[{1,Table[Sum[(n-j)*Binomial[2*j+n,j]/(2*j+n),{j,0,n}],{n,1,20}]}] (* Vaclav Kotesovec, Mar 17 2014 *)

PARI

a(n) = {my(k = 1); if(n > 0, k = sum(j = 0, n, (n-j)*binomial(2*j+n, j)/(2*j+n))); k; } \\ Jinyuan Wang, Aug 03 2019

Formula

G.f.: 1 + Sum_{n>=1} (t^n*Sum_{k=0..n} ((n-k)*binomial(2*k+n,k)/(2*k+n))).

G.f.: sqrt(3)/(sqrt(3)-2*sqrt(x)*sin(asin(3*sqrt(3x)/2)/3)). - Paul Barry, Dec 15 2006

From Gary W. Adamson, Jul 07 2011: (Start)

Let M = the production matrix:

1, 1;

1, 2, 1;

1, 3, 2, 1;

1, 4, 3, 2, 1;

1, 5, 4, 3, 2, 1;

...

a(n) is the upper left term in M^n, with sum of top row terms = a(n+1). Example: top row of M^3 = (6, 11, 5, 1), where a(3) = 6 and a(4) = 23 = (6 + 11 + 5 + 1). (End)

a(n) ~ 3^(3*n+3/2) / (49 * sqrt(Pi) * 4^n * n^(3/2)). - Vaclav Kotesovec, Mar 17 2014

Conjecture: 2*(2*n-1)*(n-1)*a(n) +3*(11*n^2-67*n+76)*a(n-1) +3*(-155*n^2+931*n-1356)*a(n-2) +(469*n^2-2799*n+4070)*a(n-3) -48*(3*n-8)*(3*n-10)*a(n-4)=0. - R. J. Mathar, May 30 2014

G.f: A(x) = 1 + series reversion of x/((1+x)*c(x/(1+x))), where c(x) = (1 - sqrt(1 - 4*x))(2*x) is the g.f. of the Catalan numbers A000108. - Peter Bala, May 05 2024