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,3

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

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

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 *)

Prog

(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

Crossrefs

Cf. A001764.

Sequence in context: A248900 A120346 A050389 * A245389 A088929 A356111

Adjacent sequences: A098743 A098744 A098745 * A098747 A098748 A098749

Keyword

nonn

Author

N. J. A. Sloane, Oct 30 2004

Status

approved