8
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ For the largest block size among all partitions of $S_n$, see math.drexel.edu/~eschmutz/PAPERS/setpartitions.pdf. $\endgroup$ Jan 9, 2012 at 19:48
  • $\begingroup$ Thanks! That's pretty interesting (even if not directly relevant...) $\endgroup$
    – Igor Rivin
    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$ Jan 9, 2012 at 23:44
  • $\begingroup$ @Brendan. Thanks! I will investigate... $\endgroup$
    – Igor Rivin
    Jan 10, 2012 at 22:31

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Cool, thanks! I will check out the references... $\endgroup$
    – Igor Rivin
    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$ 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$ Jan 10, 2012 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.