2013 | OriginalPaper | Chapter
Threshold Functions for Distinct Parts: Revisiting Erdős–Lehner
Authors : Éva Czabarka, Matteo Marsili, László A. Székely
Published in: Information Theory, Combinatorics, and Search Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 Erdős–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.