Welcome to MathOverflow

Question

6

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.

flag	asked Jan 8 2012 at 15:34 Igor Rivin 31.1k●3●37●71

1

For the largest block size among all partitions of $S_n$, see math.drexel.edu/~eschmutz/PAPERS/…. – Richard Stanley Jan 9 2012 at 19:48

Thanks! That's pretty interesting (even if not directly relevant...) – Igor Rivin Jan 9 2012 at 22:14

2

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 2012 at 23:44

@Brendan. Thanks! I will investigate... – Igor Rivin Jan 10 2012 at 22:31

Louigi Addario-Berry · Answer 1 · 2012-01-10 02:10:56Z UTC

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.

Distribution of big component of set partitions

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.