Consider the set $S_n = \{1, \dotsc, n\},$ and consider the set $P(n, k)$ of partitions of $S_n$ into $k$ parts (the cardinality of $P(n, k)$ is the Stirling number of the second kind $S(n, k).$ Define a function $M$ on $P(n, k),$ where $M(x)$ is the size of the biggest piece of the partition. Is there anything known about the distribution of the values of $M$ (as $n, k$ become large)? I assume that the answer is "yes", but am having trouble finding references.
$\begingroup$
$\endgroup$
4
asked Jan 8, 2012 at 15:34
-
1$\begingroup$ For the largest block size among all partitions of $S_n$, see math.drexel.edu/~eschmutz/PAPERS/setpartitions.pdf. $\endgroup$– Richard StanleyCommented Jan 9, 2012 at 19:48
-
$\begingroup$ Thanks! That's pretty interesting (even if not directly relevant...) $\endgroup$– Igor RivinCommented Jan 9, 2012 at 22:14
-
4$\begingroup$ A very similar problem goes by the name of occupancy, coupon collection, and various other things. Throw $n$ objects at random into $k$ bins and then look at the bin contents. There is a large literature on it (search for Corrado, for example, for a paper about the maximum and minimum bins). To relate it to your question, you need to condition on having no empty bin. This would make a large difference if $n$ is smaller than about $k\log k$, and an asymptotically negligible difference for larger $n$. In general it should be fairly routine to give asymptotic answers to your question. $\endgroup$– Brendan McKayCommented Jan 9, 2012 at 23:44
-
$\begingroup$ @Brendan. Thanks! I will investigate... $\endgroup$– Igor RivinCommented Jan 10, 2012 at 22:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
I haven't managed to find the answer to precisely your question but here are a couple of references that might be useful.
Vershik and Yakubovich have a paper on The limit shape and fluctuations of random partitions of naturals with a fixed number of summands. It addresses partitions of $n$ with around $\sqrt{n}$ summands, but doesn't seem to have exactly the result you're asking about.
If you haven't already looked at it, Chapter 1 of Pitman's Combinatorial stochastic processes seems quite relevant to your question. In particular he states something which he calls "Kolchin's representation of Gibbs partitions". For the special case of uniformly random partitions, this can be stated as follows, I think. Fix a positive parameter $\xi$ and let $X_1,X_2,\ldots$ be iid with distribution Poisson$(\xi)$ (Added on edit: the $X_i$ should be conditioned to be strictly positive). Also, let $K$ be Poisson$(e^{\xi}-1)$ and independent of the $X_i$.
Then for any $n$, conditional on the event that $X_1+\ldots+X_K=n$, the vector $(X_1,\ldots,X_K)$ is distributed as the vector of sizes of the parts of a uniformly random partition of $\{1,\ldots,n\}$, listed in exchangeable random order.
You could then try conditioning both on $X_1+\ldots+X_K=n$ and on $K=k$, and playing with the parameter $\xi$, to read off information about partitions of $\{1,\ldots,n\}$ into $k$ parts.
answered Jan 9, 2012 at 17:18
-
$\begingroup$ Cool, thanks! I will check out the references... $\endgroup$ Commented Jan 9, 2012 at 19:20
-
1$\begingroup$ Usually cells of set partitions are required to be non-empty. However, this is easy to fix and even helps since partitions into $k$ parts then correspond to the same number $k!$ of ordered partitions. Let $X_1,\ldots,X_k$ be iid random variables with distribution Poisson($\lambda$) conditioned on not being 0. Then their joint distribution conditioned on their sum being $n$ is the joint distribution of the cell sizes of a random partition. This distribution is independent of $\lambda$, so as Louigi says $\lambda$ can be selected to be useful. $\endgroup$ Commented Jan 10, 2012 at 1:17
-
$\begingroup$ Thanks for the comment, Brendan. Pitman has this right; I didn't in my first version of my answer. I'll correct. $\endgroup$ Commented Jan 10, 2012 at 2:08