OFFSET
0,3
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
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.
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
EXAMPLE
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; ...
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 *)
PROG
(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))}
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Nov 21 2011
STATUS
approved