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

1, 1, 3, 10, 34, 116, 396, 1352, 4616, 15760

Offset: 0

Author

Gus Wiseman, Mar 06 2020

Keywords

• nonn
• more

Comments

After initial terms, first differs from A291292 at a(7) = 1352, A291292(8) = 1353.

Conjectured to be the same as A007052, shifted right once.

Examples

			The a(1) = 1 through a(3) = 10 ordered set partitions:
  {{1}}  {{1,2}}    {{1,2,3}}
         {{1},{2}}  {{1},{2,3}}
         {{2},{1}}  {{1,2},{3}}
                    {{1,3},{2}}
                    {{2},{1,3}}
                    {{2,3},{1}}
                    {{3},{1,2}}
                    {{1},{2},{3}}
                    {{1},{3},{2}}
                    {{2},{1},{3}}
		

Crossrefs

Row sums of A332673.

Set partitions are A000110.

Ordered set-partitions are A000670.

Unimodal sequences covering an initial interval are A007052.

Cf. A001523, A056242, A097805, A328509, A332280, A332283, A332294, A332724.

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]],!MatchQ[#,{_,{_,a_,_},,{_,b_,_},_}/;a>b]&]],{n,0,5}]