A340598 Number of balanced set partitions of {1..n}.

0, 1, 0, 3, 3, 10, 60, 210, 700, 3556, 19845, 105567, 550935, 3120832, 19432413, 127949250, 858963105, 5882733142, 41636699676, 307105857344, 2357523511200, 18694832699907, 152228641035471, 1270386473853510, 10872532998387918, 95531590347525151

Offset

0,4

Comments

A set partition is balanced if it has exactly as many blocks as the greatest size of a block.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

Example

The a(1) = 1 through a(5) = 10 balanced set partitions (empty column indicated by dot):
  {{1}}  .  {{1},{2,3}}  {{1,2},{3,4}}  {{1},{2},{3,4,5}}
            {{1,2},{3}}  {{1,3},{2,4}}  {{1},{2,3,4},{5}}
            {{1,3},{2}}  {{1,4},{2,3}}  {{1,2,3},{4},{5}}
                                        {{1},{2,3,5},{4}}
                                        {{1,2,4},{3},{5}}
                                        {{1},{2,4,5},{3}}
                                        {{1,2,5},{3},{4}}
                                        {{1,3,4},{2},{5}}
                                        {{1,3,5},{2},{4}}
                                        {{1,4,5},{2},{3}}

Mathematica

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
Table[Length[Select[sps[Range[n]], Length[#]==Max@@Length/@#&]], {n, 0, 8}]

Prog

(PARI) \\ D(n, k) counts balanced set partitions with k blocks.
D(n, k)={my(t=sum(i=1, k, x^i/i!) + O(x*x^n)); n!*polcoef(t^k - (t-x^k/k!)^k, n)/k!}
a(n)={sum(k=sqrtint(n), (n+1)\2, D(n, k))} \\ Andrew Howroyd, Mar 14 2021

Crossrefs

The unlabeled version is A047993 (A106529).

A000110 counts set partitions.

A000670 counts ordered set partitions.

A113547 counts set partitions by maximin.

Other balance-related sequences:

- A010054 counts balanced strict integer partitions (A002110).

- A098124 counts balanced integer compositions.

- A340596 counts co-balanced factorizations.

- A340599 counts alt-balanced factorizations.

- A340600 counts unlabeled balanced multiset partitions.

- A340653 counts balanced factorizations.

Cf. A000258, A001055, A006141, A008275, A008277, A008278, A095149.

Sequence in context: A205388 A121446 A302196 * A258193 A283220 A101326

Adjacent sequences: A340595 A340596 A340597 * A340599 A340600 A340601

Keyword

nonn

Author

Gus Wiseman, Jan 20 2021

Extensions

Terms a(12) and beyond from Andrew Howroyd, Mar 14 2021

Status

approved