Partitions over Permutations

https://www.johndcook.com/blog/2026/06/04/partitions-over-permutations/

by ibobev • 2 months ago

11 1 2 months ago

this is explained by the symbolic method (https://en.wikipedia.org/wiki/Symbolic_method); in the language of exppnential generating functions, we say that bell(n) = A000110(n) = [x^n/n!] exp(exp(x)-1), since exp() means "sets of ()," exp()-1 means "nonempty sets of ()" and x means "singletons" (it can be read as "bell(n) is the # of partitions of [n] into sets of nonempty sets").

see the asymptotic formulae by Vaclav Kotesovec and Natalia L. Skirrow (me!) on https://oeis.org/A000110; the former (together with Stirling's approximation) says bell(n)/n! ~ exp(n/W(n) - nlog(W(n)) - 1) / √(τ(1+W(n))), and the latter says that the average number of subsets in a partition on [n] counted by the Bell number is ~ n/log(n), while for a permutation it's only = H_n ~ log(n).

(using W(n) ~ log(n), although it's more precisely log(n) - log(log(n)) + o(1); its appearance here comes from solving for the radius from the origin at which |exp(exp(z)-1) / z^(n+1)| has a saddle point in the complex plane, which lets you pretend your contour integral from Cauchy's formula is a Gaussian and approximate it in terms of the generating function's logarithmic second derivative)

another cool adjacent result that comes out of saddlepointery on e.g.f.s is that (# of sets of lists on [n], A000262(n))/(# of sets of cycles on [n], n!) ~ exp(2√n - 1/2)/(2√π * n^(3/4)); this is also the expected number of preimages under the surjection A000262(n) -> n! from closing lists into cycles, or equivalently the expected product of cycle lengths in a random permutation ∈ Sₙ, and is my favourite example of a function whose growth is between polynomial and exponential

Partitions over Permutations

Related Stories