Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Notation

  • Let $[n]$ denote the set of integers from 1 up to $n$, inclusive.
  • Let $A_n$ denote the average number of blocks over all partitions of $[n]$.
  • Let $B_n$ denote the number of partitions of $[n]$ (the $n$th Bell number).

Question

For any given $n \geq 1$, how small can $m$ be (as a function of $n$) and still ensure $$ A_{n-m} + 1 < A_n$$ (or, equivalently, $$ \frac{B_{n+1-m}}{B_{n-m}} < \frac{B_{n+1}}{B_n}-1)? $$

Remarks

The lefthand side of the inequality comes from fixing a particular block of size $m$ and considering all partitions of $[n]$ containing that fixed block. The idea is that if a partition contains a single large block, the expected number of blocks must fall. For my purposes, smaller values of $m$ are superior, but I would be interested to see anything.

The following reasoning led me to believe $m = \lceil n / A_n \rceil$ would be big enough. The average size of a block in a partition of $[n]$ is at most $\lceil n / A_n \rceil$. Having a single larger-than-average block should reduce the average number of blocks appearing in such a partition. Exploring with Maple shows $\lceil n / A_n \rceil$ is not quite big enough to establish the inequality, but $\lceil n / A_n \rceil + 1$ works for $n \leq 500$.

I keep mentioning averages because I'm hoping there is a quick proof of the kind I attempted in the preceding paragraph. If that vantage point is not helpful, there is the alternative statement of the inequality in terms of Bell numbers. This expression can possibly be analyzed asymptotically (though the Moser-Wyman expansion fails here), but I was rather hoping to avoid it. Still, any suggestions in this direction are welcome.

share|improve this question
    
I've no ideas or answers off-hand, been it would seem to me that $n\mapsto a(\mathcal P_n)$ is an explicit and probably very well known function of $n$. Why not just give that function explicitly, and state the question about $m$ in terms of that? Related point: the question defines but does not use the definition of $a$ applied to arbitrary collections of partitions (other than $\mathcal P_n$); is that accidental? –  Marc van Leeuwen Aug 23 '12 at 2:55
    
@MarcvanLeeuwen The function is indeed well-known and is mentioned in the post: $A_n = \frac{B_{n+1}}{B_n}−1$. The reason I do not mention it immediately is because I had hoped the answer could be easily stated without getting down to the level of Bell numbers (but this may be wishful thinking). 2. I have simplified the presentation in light of your comment. Thank you. –  Austin Mohr Aug 23 '12 at 3:36
    
Instead of $n/A_n$, perhaps a more natural bound is the average size of the block containing $1$? (This is slightly larger, though I think in the limit they become about the same). –  Kevin Costello Aug 25 '12 at 18:59
    
@KevinC. I'm not sure I appreciate the difference. Could you elaborate? –  Austin Mohr Aug 25 '12 at 22:39
    
What $A_{n-m}+1$ represents is the expected number of blocks, conditioning on the fact that the block containing $1$ is of size $m$. The average size of the block containing $1$ in a random partition is larger than the average size of a block in a random partition (larger blocks are more likely to contain $1$), which is itself larger than $n/A_n$ (Let $X$ be the number of blocks in a random set partition. By Jensen's inequality $E(n/X)>n/E(X)$). But the differences don't seem large -- for $n=5$ we have $n/A_n=1.72$, average block size is $1.88$, average size of the "1" block is $2.15$. –  Kevin Costello Aug 26 '12 at 0:07

1 Answer 1

up vote 3 down vote accepted
+200

We can think of a partition of $[n+1]$ as being formed by taking a parent partition of $[n]$ and either adding $n+1$ to an existing set or putting it in as a new set (so each parent with $k$ blocks has $k$ children with $k$ blocks and $1$ child with $k+1$ blocks; this is the same coupling used in Mike Spivey's answer to this question). If we let $X_n$ denote the number of blocks in a random partition of $[n]$ (so $A_n=E(X_n)$), this gives

\begin{eqnarray*} A_{n+1} &=& \frac{\sum_k (k^2+(k+1)) P(X_n=k)}{\sum_k (k+1) P(X_n=k)} \\ &=& \frac{E(X_n^2)+ A_n+1}{A_n+1} \\ &\geq& \frac{A_n^2+A_n+1}{A_n+1} \textrm{ (since } E(X_n^2) \geq (E(X_n))^2 \textrm{)}\\ &=& A_n+\frac{1}{A_n+1} \end{eqnarray*}

So inductively we have $$A_{n}-A_{n-m} \geq \sum_{j=n-m}^{n-1} \frac{1}{A_j+1} \geq \frac{m}{A_{n-1}+1}$$ since $A_j$ is non-decreasing (as was shown in the linked question). It follows we can take $m=\lceil A_{n-1}+1 \rceil$.


As was noted in the comments, this bound is far from tight. If you're interested in asymptotic bounds, then one possibility may be to leave in the term I left out, writing $$A_{n+1}=A_n+\frac{1}{A_n+1}+\frac{Var(X_n)}{A_n+1}.$$ Both $A_n$ and the variance seem to be well-studied -- Theorem 8.60 of Toufik Mansour's recent book (referencing Theorem VIII.41 in Flajolet and Sedgwick's Analytic Combinatorics) gives their values as $\frac{n}{\log n}(1+o(1))$ and $\frac{n}{\log^2 n} (1+o(1))$ respectively, which would give you $m=\log n$ asymptotically.

share|improve this answer
1  
This is very nice. I didn't think the answer would be so straightforward -- well done! –  joriki Aug 28 '12 at 22:50
1  
This is indeed the kind of argument I've been trying to get through. Thank you very much for your insight! I will mention (not for lack of gratitude, but for future readers of this question) this line of attack gives a much larger $m$ than is necessary. Take $N = 400$ for example. The $m$ suggested by this solution is 89, while the smallest $m$ satisfying the inequality is actually 6. My (mostly unjustified) conjecture is $m = ln(n)$ is already large enough. –  Austin Mohr Aug 29 '12 at 2:40
1  
That is a rather large difference. I had thought when answering that because $X_n$ was concentrated around its expectation (with high probability $X_n/E(X_n)$ is close to $1$) that replacing $E(X_n^2)$ by $A_n^2$ wouldn't lose too much. But I guess all that really says is that I have a good approximation to $A_{n+1}$, and an error that's a tiny fraction of $A_{n+1}$ can be a huge fraction of $A_{n+1}-A_n$. –  Kevin Costello Aug 29 '12 at 3:37

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.