A332724 Number of length n - 1 ordered set partitions of {1..n} where no element of any block is greater than any element of a non-adjacent consecutive block.

0, 0, 1, 6, 14, 32, 65, 128, 243, 452, 826, 1490, 2659, 4704, 8261, 14418, 25030, 43252, 74437, 127648, 218199, 371920, 632306, 1072486, 1815239, 3066432, 5170825, 8705118, 14632958, 24562952, 41177801, 68947520, 115313979, 192656924, 321554986, 536191418

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) = A001629(n) + 4*A001629(n+1) + A001629(n+2) for n > 0.

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

Column k = n - 1 of A332673, which has row-sums A332872.

Ordered set-partitions are A000670.

Unimodal compositions are A001523.

Unimodal normal sequences appear to be A007052.

Non-unimodal normal sequences are A328509.

Cf. A000045, A001286, A001629, A056242, A227038, A332577.

Sequence in context: A271996 A199705 A225972 * A078836 A340735 A142875

Adjacent sequences: A332721 A332722 A332723 * A332725 A332726 A332727

Keyword

nonn

Author

Gus Wiseman, Mar 03 2020

Extensions

Terms a(9) and beyond from Andrew Howroyd, Apr 17 2021

Status

approved