Partitions over Permutations
2 days ago
- #Mathematics
- #Bell Numbers
- #Asymptotic Analysis
- The post discusses a cosine approximation to the Gaussian function exp(−z²) and compares it with (1 + cos(sin(z) + z))/2, noting they are close along the real axis but not along the imaginary axis, where the right side grows much faster, behaving like exp(exp(y)).
- The power series for exp(exp(y)) is explored, with coefficients involving Bell numbers Bn, where the nth coefficient is e Bn / n!, and Bn represents the number of ways to partition a set of n labeled items.
- The ratio of partitions to permutations for a set of n labeled items, Bn/n!, is computed using SymPy, highlighting that Bell numbers grow almost as fast as permutations, leading to slow convergence of the series.
- Asymptotic analysis shows log(Bn/n!) ~ ½ log n − n log log n and involves the Lambert W function, with r = W(n) in the formula log(Bn/n!) ~ n/r − 1 − n log r.
- Related points include the distinction between Bell numbers for labeled sets and partition numbers for unlabeled sets, and the note that exp(exp(x)-1) is the exponential generating function for Bell numbers, being slightly more natural with value 1 at x=0 and eliminating the extra e in coefficients.