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

1, 1, 2, 6, 22, 89, 381, 1694, 7744, 36168, 171831, 827814, 4034589, 19857262, 98555324, 492710856, 2478897620, 12541604830, 63768192378, 325674039636, 1669922290311, 8593644472017, 44369362778645, 229767801472366, 1193126351099007, 6211253430642091

Offset: 0

Author

Paul D. Hanna, Nov 21 2011

Keywords

• nonn

Comments

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

Concerning the previous comment: This was proved by Mansour and Shattuck. - Eric M. Schmidt, Jul 18 2017

Examples

			G.f.: A(x) = 1 + x + 2*x^2 + 6*x^3 + 22*x^4 + 89*x^5 + 381*x^6 + ...
Related expansion:
A(x)^3 = 1 + 3*x + 9*x^2 + 31*x^3 + 120*x^4 + 501*x^5 + 2195*x^6 + ...
where a(2) = 3 - 1; a(3) = 9 - 3; a(4) = 31 - 9; a(5) = 120 - 31; ...
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Beáta Bényi, Toufik Mansour, and José L. Ramírez, Pattern Avoidance in Weak Ascent Sequences, arXiv:2309.06518 [math.CO], 2023.
• Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, Patterns in Inversion Sequences I, arXiv:1510.05434 [math.CO], 2015.
• Toufik Mansour and Mark Shattuck, Pattern avoidance in inversion sequences, Pure Mathematics and Applications, 25(2):157-176, 2015.
• Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
• Jay Pantone, The enumeration of inversion sequences avoiding the patterns 201 and 210, arXiv:2310.19632 [math.CO], 2023.
• Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024. See p. 2.

Crossrefs

Cf. A001764, A200754.

Programs

Mathematica

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

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

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

PARI

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

Formula

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

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

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

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

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

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

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