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

%I #91 Jul 07 2024 01:33:07

%S 1,1,2,6,23,102,495,2549,13682,75714,428882,2474573,14492346,85926361,

%T 514763279,3111119358,18946375767,116147683902,716179441293,

%U 4438862153246,27638747494178,172805469880497,1084462349973559,6828717036765622,43132158190994223,273204023401012901

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

%C (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

%C 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

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

%H G. C. Greubel, <a href="/A098746/b098746.txt">Table of n, a(n) for n = 0..1000</a>

%H M. H. Albert et al., <a href="http://dx.doi.org/10.1016/j.disc.2004.08.003">Restricted permutations and queue jumping</a>, Discrete Math., 287 (2004), 129-133.

%H Paul Barry, <a href="https://arxiv.org/abs/1912.11845">Chebyshev moments and Riordan involutions</a>, arXiv:1912.11845 [math.CO], 2019.

%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.

%H Wlodzimierz Bryc, Raouf Fakhfakh, and Wojciech Mlotkowski, <a href="https://arxiv.org/abs/1708.05343">Cauchy-Stieltjes families with polynomial variance functions and generalized orthogonality</a>, arXiv:1708.05343 [math.PR], 2017-2019. Also in <a href="http://www.math.uni.wroc.pl/~pms/publicationsArticleRef.php?nr=39.2&amp;nrA=1&amp;ppB=%20237&amp;ppE=%20258">Probability and Mathematical Statistics</a> (2019), Vol. 39, No. 2, 237-258.

%H Wenqin Cao, Emma Yu Jin, and Zhicong Lin, <a href="https://doi.org/10.1016/j.dam.2019.01.035">Enumeration of inversion sequences avoiding triples of relations</a>, Discrete Applied Mathematics (2019); see also <a href="http://www.emmayujin.at/Pubs/CaoJinLin19.pdf">author's copy</a>.

%H Joanna N. Chen and Zhicong Lin, <a href="https://arxiv.org/abs/2112.04115">Combinatorics of the symmetries of ascents in restricted inversion sequences</a>, arXiv:2112.04115 [math.CO], 2021.

%H Isaac DeJager, Madeleine Naquin, and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.

%H Toufik Mansour and Mark Shattuck, <a href="https://hal.archives-ouvertes.fr/hal-03295362">Further enumeration results concerning a recent equivalence of restricted inversion sequences</a>, hal-03295362 [math.CO], 2021.

%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016 [Section 2.26].

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

%F G.f.: sqrt(3)/(sqrt(3)-2*sqrt(x)*sin(asin(3*sqrt(3x)/2)/3)). - _Paul Barry_, Dec 15 2006

%F From _Gary W. Adamson_, Jul 07 2011: (Start)

%F Let M = the production matrix:

%F 1, 1;

%F 1, 2, 1;

%F 1, 3, 2, 1;

%F 1, 4, 3, 2, 1;

%F 1, 5, 4, 3, 2, 1;

%F ...

%F 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)

%F a(n) ~ 3^(3*n+3/2) / (49 * sqrt(Pi) * 4^n * n^(3/2)). - _Vaclav Kotesovec_, Mar 17 2014

%F 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

%F 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

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

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

%o (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

%Y Cf. A000108, A001764.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, Oct 30 2004