|
%I #31 Oct 07 2021 10:46:21
%S 1,1,2,4,10,26,73,214,651,2040,6549,21453,71485,241702,827603,2865087,
%T 10014927,35307628,125427569,448616693,1614432373,5842129120,
%U 21247505098,77631329535,284832049361,1049092809734,3877749157355,14380314221305,53490244751332
%N Number of length n inversion sequences avoiding the patterns 000, 010, 110, 120, and 210.
%C 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<j<k) such that e_j >= e_k and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 000, 010, 110, 120, and 210.
%H Alois P. Heinz, <a href="/A279544/b279544.txt">Table of n, a(n) for n = 0..600</a>
%H Megan A. Martinez, 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.
%F a(n) ~ c * 4^n / n^(3/2), where c = 0.0549097036253448014962069269284638611865763295943683310517... - _Vaclav Kotesovec_, Oct 07 2021
%e For n=3, the inversion sequences are 001, 002, 011, 012.
%p b:= proc(n, i, m) option remember; `if`(i=0, 1, add(
%p b(n-min(m, j), i-1, abs(m-j)), j=1..n-i+1))
%p end:
%p a:= n-> b(n$2, 0):
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Dec 15 2016
%t b[n_, i_, m_] := b[n, i, m] = If[i == 0, 1, Sum[b[n - Min[m, j], i - 1, Abs[m - j]], {j, 1, n - i + 1}]];
%t a[n_] := b[n, n, 0];
%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 10 2017, after _Alois P. Heinz_ *)
%Y Cf. A000085, A263777, A263778, A263779, A263780.
%K nonn
%O 0,3
%A _Megan A. Martinez_, Dec 14 2016
%E a(10)-a(28) from _Alois P. Heinz_, Dec 14 2016
|
