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

1, 1, 1, 4, 10, 46, 166, 827, 3795, 20645, 112124, 672673, 4163743, 27565188, 190168577, 1381763398, 10468226150, 82844940414, 681863474058, 5832378929502, 51720008131148, 474862643822274, 4506628734688128, 44151853623626218, 445956917001833090, 4638586880336637692

Offset

0,4

Comments

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.

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.

This is different from separable partitions (A325534) and partitions of separable type (A336106).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..250

Example

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

Mathematica

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
stnseps[stn_]:=Select[Permutations[Union@@stn], And@@Table[Position[stn, #[[i]]][[1, 1]]!=Position[stn, #[[i+1]]][[1, 1]], {i, Length[#]-1}]&]
Table[Length[Select[sps[Range[n]], stnseps[#]!={}&]], {n, 0, 5}]

Crossrefs

For separable partitions see A386583, sums A325534, ranks A335433.

For inseparable partitions see A386584, sums A325535, ranks A335448.

For separable type partitions see A386585, sums A336106, ranks A335127.

For inseparable type partitions see A386586, sums A386638 or A025065, ranks A335126.

The complement is counted by A386634, sums of A386636.

Row sums of A386635.

A000110 counts set partitions, row sums of A048993.

A000670 counts ordered set partitions.

A003242 and A335452 count anti-runs, ranks A333489, patterns A005649.

A279790 counts disjoint families on strongly normal multisets.

A335434 counts separable factorizations, inseparable A333487.

A336103 counts normal separable multisets, inseparable A336102.

Cf. A001055, A072233, A106351, A190945, A239455, A239964, A335125, A386575, A386578, A386580, A386587.

Sequence in context: A149228 A149229 A149230 * A115327 A233395 A197664

Adjacent sequences: A386630 A386631 A386632 * A386634 A386635 A386636

Keyword

nonn

Author

Gus Wiseman, Aug 09 2025

Extensions

a(12)-a(25) from Alois P. Heinz, Aug 10 2025

Status

approved