A356957 Number of set partitions of strict integer partitions of n into intervals, where an interval is a set of positive integers with all differences of adjacent elements equal to 1.

1, 1, 1, 3, 2, 4, 7, 7, 8, 13, 20, 19, 27, 30, 42, 60, 63, 75, 99, 112, 141, 191, 205, 248, 296, 357, 408, 513, 617, 696, 831, 969, 1117, 1337, 1523, 1797, 2171, 2420, 2805, 3265, 3772, 4289, 5013, 5661, 6579, 7679, 8615, 9807, 11335, 12799, 14581

Offset

0,4

Links

Table of n, a(n) for n=0..50.

Example

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

Mathematica

chQ[y_] := Length[y] <= 1 || Union[Differences[y]] == {1};
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
Table[Length[Select[Join@@sps/@Reverse/@Select[IntegerPartitions[n], UnsameQ@@#&], And@@chQ/@#&]], {n, 0, 15}]

Crossrefs

Intervals are counted by A000012, A001227, ranked by A073485.

The initial version is A010054.

For set partitions of {1..n} we have A011782.

The non-strict version is A107742

Not restricting to intervals gives A294617.

More types: A356936, A356937, A356938, A356939, A356940.

A000041 counts integer partitions, strict A000009.

A000110 counts set partitions.

A001970 counts multiset partitions of integer partitions.

A356941 counts multiset partitions of integer partitions w/ gapless blocks.

Cf. A001055, A055887, A061260, A270995, A304969, A349050, A349055.

Sequence in context: A276954 A276944 A300501 * A158441 A349368 A376183

Adjacent sequences: A356954 A356955 A356956 * A356958 A356959 A356960

Keyword

nonn

Author

Gus Wiseman, Sep 13 2022

Status

approved