A386635 Triangle read by rows where T(n,k) is the number of separable type set partitions of {1..n} into k blocks.

1, 0, 1, 0, 0, 1, 0, 0, 3, 1, 0, 0, 3, 6, 1, 0, 0, 10, 25, 10, 1, 0, 0, 10, 75, 65, 15, 1, 0, 0, 35, 280, 350, 140, 21, 1, 0, 0, 35, 770, 1645, 1050, 266, 28, 1, 0, 0, 126, 2737, 7686, 6951, 2646, 462, 36, 1, 0, 0, 126, 7455, 32725, 42315, 22827, 5880, 750, 45, 1

Offset: 0

Author

Gus Wiseman, Aug 10 2025

Keywords

• nonn
• tabl

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 blocks sizes.

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

Examples

			Row n = 4 counts the following set partitions:
  .  .  {{1,2},{3,4}}  {{1},{2},{3,4}}  {{1},{2},{3},{4}}
        {{1,3},{2,4}}  {{1},{2,3},{4}}
        {{1,4},{2,3}}  {{1},{2,4},{3}}
                       {{1,2},{3},{4}}
                       {{1,3},{2},{4}}
                       {{1,4},{2},{3}}
Triangle begins:
    1
    0    1
    0    0    1
    0    0    3    1
    0    0    3    6    1
    0    0   10   25   10    1
    0    0   10   75   65   15    1
    0    0   35  280  350  140   21    1
		

Crossrefs

Column k = 2 appears to be A128015.

For separable partitions we have A386583, sums A325534, ranks A335433.

For inseparable partitions we have A386584, sums A325535, ranks A335448.

For separable type partitions we have A386585, sums A336106, ranks A335127.

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

Row sums are A386633.

The complement is counted by A386636, row sums A386634.

A000110 counts set partitions, row sums of A048993.

A000670 counts ordered set partitions.

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

A239455 counts Look-and-Say partitions, ranks A351294, conjugate A381432.

A335434 counts separable factorizations, inseparable A333487.

A336103 counts normal separable multisets, inseparable A336102.

A351293 counts non-Look-and-Say partitions, ranks A351295, conjugate A381433.

A386587 counts disjoint families of strict partitions of each prime exponent.

Cf. A072233, A097805, A106351, A116861, A190945, A279790, A333382, A335125, A374252, A386575, A386578.

Programs

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]],Length[#]==k&&stnseps[#]!={}&]],{n,0,5},{k,0,n}]