OFFSET
0,4
COMMENTS
In other words, parts of not-immediately-subsequent blocks are increasing.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).
FORMULA
From Andrew Howroyd, Apr 17 2021: (Start)
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4) for n > 4.
G.f.: x*(1 + 4*x + x^2)/(1 - x - x^2)^2.
(End)
EXAMPLE
The a(2) = 1 through a(4) = 14 ordered set partitions:
{{1,2}} {{1},{2,3}} {{1},{2},{3,4}}
{{1,2},{3}} {{1},{2,3},{4}}
{{1,3},{2}} {{1,2},{3},{4}}
{{2},{1,3}} {{1},{2,4},{3}}
{{2,3},{1}} {{1,2},{4},{3}}
{{3},{1,2}} {{1},{3},{2,4}}
{{1,3},{2},{4}}
{{1},{3,4},{2}}
{{1},{4},{2,3}}
{{2},{1},{3,4}}
{{2},{1,3},{4}}
{{2},{1,4},{3}}
{{2,3},{1},{4}}
{{3},{1,2},{4}}
MATHEMATICA
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
Table[Length[Select[Join@@Permutations/@sps[Range[n]], Length[#]==n-1&&!MatchQ[#, {___, {___, a_, ___}, __, {___, b_, ___}, ___}/; a>b]&]], {n, 0, 8}]
PROG
(PARI) \\ here b(n) is A001629(n).
b(n) = {((n+1)*fibonacci(n-1) + (n-1)*fibonacci(n+1))/5}
a(n) = {if(n==0, 0, b(n) + 4*b(n-1) + b(n-2))} \\ Andrew Howroyd, Apr 17 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 03 2020
EXTENSIONS
Terms a(9) and beyond from Andrew Howroyd, Apr 17 2021
STATUS
approved