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

Author

Gus Wiseman, Mar 03 2020

Keywords

• nonn

Comments

In other words, parts of not-immediately-subsequent blocks are increasing.

Examples

			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}}
		

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).

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.

Programs

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}]

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

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)

Extensions

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