10
$\begingroup$

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.

  • 0
    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?2012-08-23
  • 0
    @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.2012-08-23
  • 0
    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).2012-08-25
  • 0
    @KevinC. I'm not sure I appreciate the difference. Could you elaborate?2012-08-25
  • 0
    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$.2012-08-26
  • 0
    @KevinCostello I believe $n / A_n$ is exactly the average block size. The sum of all block sizes is $nB_n$ (each partition has $n$ elements and there are $B_n$ of them). The number of blocks appearing across all partitions is $\sum_{k=1}^n k S(n,k)$, where $S(n,k)$ is the Stirling Number of the 2nd kind (for each $k$, each partition counted by $S(n,k)$ contributes exactly $k$ blocks). The ratio of the former to the latter is $1.72$ for $n = 5$, which is the same as $5 / A_5$.2012-08-27
  • 0
    $1.72$ is the average size of a block if you chose a block at random across all partitions, but $1.88$ is the average size of a block if you choose a partition at random then choose a block from that partition. If we condition on the block containing 1 being size 2, then the six possible partitions are $\{12,34\}$, $\{12,3,4\}$, $\{13,24\}$, $\{13,2,4\}$, $\{14,23\}$, and $\{14,2,3\}$, so the average number of blocks is $15/6=5/2=3/2+1$.2012-08-27
  • 0
    @KevinCostello I see my both my error from last night (inability to count) and the difference in our points of view (picking first a partition and then a block, instead of weighing all blocks equally). Thank you for your perspective.2012-08-27

1 Answers 1

4

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.

  • 1
    This is very nice. I didn't think the answer would be so straightforward -- well done!2012-08-28
  • 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.2012-08-29
  • 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$.2012-08-29