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

Author

Gus Wiseman, Jan 20 2021

Keywords

• nonn

Comments

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

Examples

			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}}
		

Links

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

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.

Programs

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}]

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

Extensions

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