Threshold Functions for Distinct Parts: Revisiting Erdos-Lehner

摘要

We study four problems: put n distinguishable/non-distinguishable balls into k non-empty distinguishable/non-distinguishable boxes randomly. What is the threshold function k = k(n) to make almost sure that no two boxes contain the same number of balls? The non-distinguishable ball problems are very close to the Erdos-Lehner asymptotic formula for the number of partitions of the integer n into k parts with k = o(n~(1/3)). The problem is motivated by the statistics of an experiment, where we only can tell whether outcomes are identical or different.