login
A328425
Number of inversion sequences of length n where all consecutive subsequences i,j,k satisfy i < j > k or i >= j <= k.
5
1, 1, 2, 4, 11, 36, 142, 647, 3383, 19816, 129162, 923279, 7201951, 60720996, 551268926, 5352973967, 55430433719, 609033864160, 7083303687843, 86864585123112, 1120997775904467, 15176639841694385, 215196709973260722, 3187766448289854016, 49262381105608795771
OFFSET
0,3
LINKS
Juan S. Auli and Sergi Elizalde, Consecutive patterns in inversion sequences II: avoiding patterns of relations, arXiv:1906.07365 [math.CO], 2019.
FORMULA
a(n) ~ n! * c * 2^n * n^(Pi/4 - 1/2) / Pi^n, where c = 1.60233729528... - Vaclav Kotesovec, Oct 31 2019
EXAMPLE
a(0) = 1: the empty sequence.
a(1) = 1: 0.
a(2) = 2: 00, 01.
a(3) = 4: 000, 001, 002, 010.
a(5) = 11: 0000, 0001, 0002, 0003, 0010, 0020, 0021, 0100, 0101, 0102, 0103.
a(6) = 36: 00000, 00001, 00002, 00003, 00004, 00010, 00020, 00021, 00030, 00031, 00032, 00100, 00101, 00102, 00103, 00104, 00200, 00201, 00202, 00203, 00204, 00211, 00212, 00213, 00214, 01000, 01001, 01002, 01003, 01004, 01010, 01020, 01021, 01030, 01031, 01032.
MAPLE
b:= proc(n, j, t, c) option remember; `if`(n=0, 1, add(`if`((i<j
xor t) and c=0, 0, b(n-1, i, is(i>j), max(0, c-1))), i=1..n))
end:
a:= n-> b(n, 0, true, 2):
seq(a(n), n=0..24);
MATHEMATICA
b[n_, j_, t_, c_] := b[n, j, t, c] = If[n == 0, 1, Sum[If[Xor[i < j, t] && c == 0, 0, b[n - 1, i, i > j, Max[0, c - 1]]], {i, 1, n}]];
a[n_] := b[n, 0, True, 2];
a /@ Range[0, 24] (* Jean-François Alcover, Feb 26 2020, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Oct 15 2019
STATUS
approved