Partitions over permutations
I was thinking more about the cosine approximation to the Gaussian
exp(-z^2) (1 + cos(sin(z) +z))/2
that I wrote about last week. The two expressions above are close along the real axis but not along the imaginary axis.
Ifz =iy, the right side grows much faster than the left, behaving likeexp(exp(y)).
This led to me looking up the power series for the double exponential function exp(exp(y)). This is an interesting series because the coefficient of xn is
e Bn / n!
where Bn is the nth Bell number, which equals the number of ways to partition a set ofn labeled items [1]. And of course n! is the number of ways to permute a set ofn labeled items. So the nth coefficient in the power series for exp(exp(y)) is the ratio of the number of partitions to permutations for a set ofn labeled things, multiplied by e.
The number of ways to partition a set ofn things grows quickly asn increases, almost as quickly as the number of permutations, and so the series for the double exponential function converges very slowly.
ComputingSymPy has a function bell for computing Bell numbers, so you could compute the ratio of partitions to permutations as follows.
from sympy import bell, factorialf = lambda n: bell(n)/factorial(n)
This returns a number of type sympy.core.numbers.Rational and so the result is exact. You can cast it to float for convenience.
AsymptoticsIf we look at only the terms in the asymptotic series for log Bn and logn! that grow withn we have
log Bn ~ n logn -n log logn
logn! ~n logn - log n
and so
log( Bn /n! ) ~ log n -n log logn
There's also an asymptotic series for log( Bn /n! ) involving the LambertW function:
log( Bn /n! ) ~n/r - 1 - n log r
wherer = W(n).
Related posts[1] It's important that the items are labeled. Partition numbers are the number of partitions of anunlabeled set. Partition numbers are much smaller than Bell numbers.
The post Partitions over permutations first appeared on John D. Cook.