Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
For the largest block size among all partitions of $S_n$, see math.drexel.edu/~eschmutz/PAPERS/setpartitions.pdf. –  Richard Stanley Jan 9 '12 at 19:48
    
Thanks! That's pretty interesting (even if not directly relevant...) –  Igor Rivin Jan 9 '12 at 22:14
3  
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. –  Brendan McKay Jan 9 '12 at 23:44
    
@Brendan. Thanks! I will investigate... –  Igor Rivin Jan 10 '12 at 22:31
add comment

1 Answer 1

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.

share|improve this answer
    
Cool, thanks! I will check out the references... –  Igor Rivin Jan 9 '12 at 19:20
1  
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. –  Brendan McKay Jan 10 '12 at 1:17
    
Thanks for the comment, Brendan. Pitman has this right; I didn't in my first version of my answer. I'll correct. –  Louigi Addario-Berry Jan 10 '12 at 2:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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