A200753 - OEIS

%I #53 Jul 15 2024 10:37:29

%S 1,1,2,6,22,89,381,1694,7744,36168,171831,827814,4034589,19857262,

%T 98555324,492710856,2478897620,12541604830,63768192378,325674039636,

%U 1669922290311,8593644472017,44369362778645,229767801472366,1193126351099007,6211253430642091

%N G.f. satisfies: A(x) = 1 + (x-x^2)*A(x)^3.

%C S. Corteel et al. ask whether this sequence also gives the number of inversion sequences avoiding the pattern 102. - _Michel Marcus_, Oct 26 2015

%C Concerning the previous comment: This was proved by Mansour and Shattuck. - _Eric M. Schmidt_, Jul 18 2017

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

%H Beáta Bényi, Toufik Mansour, and José L. Ramírez, <a href="https://arxiv.org/abs/2309.06518">Pattern Avoidance in Weak Ascent Sequences</a>, arXiv:2309.06518 [math.CO], 2023.

%H Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, <a href="http://arxiv.org/abs/1510.05434">Patterns in Inversion Sequences I</a>, arXiv:1510.05434 [math.CO], 2015.

%H Toufik Mansour and Mark Shattuck, <a href="https://doi.org/10.1515/puma-2015-0016">Pattern avoidance in inversion sequences</a>, Pure Mathematics and Applications, 25(2):157-176, 2015.

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

%H Jay Pantone, <a href="https://arxiv.org/abs/2310.19632">The enumeration of inversion sequences avoiding the patterns 201 and 210</a>, arXiv:2310.19632 [math.CO], 2023.

%H Benjamin Testart, <a href="https://arxiv.org/abs/2407.07701">Completing the enumeration of inversion sequences avoiding one or two patterns of length 3</a>, arXiv:2407.07701 [math.CO], 2024. See p. 2.

%F a(n) = Sum_{k=0..[n/2]} (-1)^k * C(n-k, k) * C(3*(n-k), n-k) / (2*(n-k)+1).

%F G.f.: A(x) = G(x-x^2) where G(x) = 1 + x*G(x)^3 is the g.f. for A001764.

%F G.f.: A(x) = (1/x)*Series_Reversion( x*(1+x^2 + sqrt((1+x^2)^2 - 4*x))/2 ).

%F G.f.: A(x) = (1 - x^2*A(x)^3) / (1 - x*A(x)^2).

%F Conjecture: 2n*(2n+1)*a(n) -(13n-7)(3n-2)*a(n-1) +4(29n^2-87n+67)*a(n-2) +9(-15n^2+69n-80)*a(n-3) +6(3n-8)(3n-10)*a(n-4)=0. - _R. J. Mathar_, Nov 22 2011

%F Recurrence: 2*(n-1)*n*(2*n+1)*a(n) = (n-1)*(31*n^2 - 27*n + 6)*a(n-1) - 6*(9*n^3 - 27*n^2 + 22*n - 2)*a(n-2) + 3*n*(3*n-7)*(3*n-5)*a(n-3). - _Vaclav Kotesovec_, Aug 19 2013

%F a(n) ~ sqrt(18*sqrt(33)-66) * ((27+3*sqrt(33))/8)^n/(16*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Aug 19 2013

%e G.f.: A(x) = 1 + x + 2*x^2 + 6*x^3 + 22*x^4 + 89*x^5 + 381*x^6 + ...

%e Related expansion:

%e A(x)^3 = 1 + 3*x + 9*x^2 + 31*x^3 + 120*x^4 + 501*x^5 + 2195*x^6 + ...

%e where a(2) = 3 - 1; a(3) = 9 - 3; a(4) = 31 - 9; a(5) = 120 - 31; ...

%t Table[Sum[(-1)^k*Binomial[n-k,k]*Binomial[3*(n-k),n-k]/(2*(n-k)+1),{k,0,Floor[n/2]}],{n,0,20}] (* _Vaclav Kotesovec_, Aug 19 2013 *)

%o (PARI) {a(n)=local(A=1+x);for(i=1,n,A=1+(x-x^2)*A^3+x*O(x^n));polcoeff(A,n)}

%o (PARI) {a(n)=polcoeff((1/x)*serreverse( x*(1+x^2 + sqrt((1+x^2)^2 - 4*x +x^2*O(x^n)))/2 ),n)}

%o (PARI) {a(n)=sum(k=0,n\2,(-1)^k*binomial(n-k, k)*binomial(3*(n-k),n-k)/(2*(n-k)+1))}

%Y Cf. A001764, A200754.

%K nonn

%O 0,3

%A _Paul D. Hanna_, Nov 21 2011