cp's OEIS Frontend

A386633 Number of separable type set partitions of {1..n}.

%I A386633 #18 Aug 11 2025 14:37:52
%S A386633 1,1,1,4,10,46,166,827,3795,20645,112124,672673,4163743,27565188,
%T A386633 190168577,1381763398,10468226150,82844940414,681863474058,
%U A386633 5832378929502,51720008131148,474862643822274,4506628734688128,44151853623626218,445956917001833090,4638586880336637692
%N A386633 Number of separable type set partitions of {1..n}.
%C A386633 A set partition is of separable type iff the underlying set has a permutation whose adjacent elements always belong to different blocks. Note that this only depends on the sizes of the blocks.
%C A386633 A set partition is also of separable type iff its greatest block size is at most one more than the sum of all its other block sizes.
%C A386633 This is different from separable partitions (A325534) and partitions of separable type (A336106).
%H A386633 Alois P. Heinz, <a href="/A386633/b386633.txt">Table of n, a(n) for n = 0..250</a>
%e A386633 The a(1) = 1 through a(4) = 10 set partitions:
%e A386633   {{1}}  {{1},{2}}  {{1},{2,3}}    {{1,2},{3,4}}
%e A386633                     {{1,2},{3}}    {{1,3},{2,4}}
%e A386633                     {{1,3},{2}}    {{1,4},{2,3}}
%e A386633                     {{1},{2},{3}}  {{1},{2},{3,4}}
%e A386633                                    {{1},{2,3},{4}}
%e A386633                                    {{1,2},{3},{4}}
%e A386633                                    {{1},{2,4},{3}}
%e A386633                                    {{1,3},{2},{4}}
%e A386633                                    {{1,4},{2},{3}}
%e A386633                                    {{1},{2},{3},{4}}
%t A386633 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A386633 stnseps[stn_]:=Select[Permutations[Union@@stn],And@@Table[Position[stn,#[[i]]][[1,1]]!=Position[stn,#[[i+1]]][[1,1]],{i,Length[#]-1}]&]
%t A386633 Table[Length[Select[sps[Range[n]],stnseps[#]!={}&]],{n,0,5}]
%Y A386633 For separable partitions see A386583, sums A325534, ranks A335433.
%Y A386633 For inseparable partitions see A386584, sums A325535, ranks A335448.
%Y A386633 For separable type partitions see A386585, sums A336106, ranks A335127.
%Y A386633 For inseparable type partitions see A386586, sums A386638 or A025065, ranks A335126.
%Y A386633 The complement is counted by A386634, sums of A386636.
%Y A386633 Row sums of A386635.
%Y A386633 A000110 counts set partitions, row sums of A048993.
%Y A386633 A000670 counts ordered set partitions.
%Y A386633 A003242 and A335452 count anti-runs, ranks A333489, patterns A005649.
%Y A386633 A279790 counts disjoint families on strongly normal multisets.
%Y A386633 A335434 counts separable factorizations, inseparable A333487.
%Y A386633 A336103 counts normal separable multisets, inseparable A336102.
%Y A386633 Cf. A001055, A072233, A106351, A190945, A239455, A239964, A335125, A386575, A386578, A386580, A386587.
%K A386633 nonn
%O A386633 0,4
%A A386633 _Gus Wiseman_, Aug 09 2025
%E A386633 a(12)-a(25) from _Alois P. Heinz_, Aug 10 2025