A279560 Number of length n inversion sequences avoiding the patterns 100, 210, 201, and 102.

1, 1, 2, 6, 21, 76, 277, 1016, 3756, 13998, 52554, 198568, 754316, 2878552, 11027384, 42384412, 163372325, 631290168, 2444700421, 9485463044, 36866810877, 143508889270, 559399074443, 2183269032876, 8530724152279, 33366805383326, 130633854520329, 511889287682280

Offset: 0

Author

Megan A. Martinez, Jan 17 2017

Keywords

• nonn

Comments

A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i e_j and e_i <> e_k. This is the same as the set of length n inversion sequences avoiding 100, 210, 201, and 102.

Examples

			The length 4 inversion sequences avoiding (100, 210, 201, 102) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0101, 0110, 0111, 0112, 0113, 0120, 0121, 0122, 0123.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1665
• Megan A. Martinez, Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.

Crossrefs

Cf. A000108, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.

Programs

Maple

a:= proc(n) option remember; `if`(n<4, n!,
     ((6*(9*n^4-61*n^3+100*n^2+52*n-140))*a(n-1)
     -(3*(3*n-8))*(9*n^3-38*n^2+3*n+70)*a(n-2)
     +(2*(2*n-7))*(9*n^3-31*n^2-2*n+60)*a(n-3))
      / ((9*n^3-58*n^2+87*n+22)*n))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 24 2017

Mathematica

a[0] = 1; a[n_] := Binomial[2n-2, n-1] + Sum[(4i Binomial[2i+1, i+1]) / ((i+2)(i+3)), {k, 2, n-2}, {i, 1, k-1}]; Array[a, 30, 0] (* Jean-François Alcover, Nov 06 2017 *)

PARI

a(n) = if (n==0, 1, binomial(2*n-2,n-1) + sum(k=2, n-2, sum(i=1,k-1, sum(u=1, i, sum(d=0, u-1, ((i-d+1)/(i+1)*binomial(i+d,d))))))); \\ Michel Marcus, Jan 18 2017

Formula

a(n) = binomial(2n-2,n-1) + Sum_{k=2..n-2} Sum_{i=1..k-1} Sum_{u=1..i} Sum_{d=0..u-1} ((i-d+1)/(i+1)*binomial(i+d,d)) for n>0, a(0)=1.

a(n) ~ 4^(n-1) / sqrt(Pi*n). - Vaclav Kotesovec, Oct 07 2021

Extensions

More terms from Michel Marcus, Jan 18 2017