MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S_{n,r}$ denote the Stirling number of the second kind. Define $A_{n,r}:=\frac{\binom{n+r-1}{n}(n+r)!}{S_{n+r,r}r!}$. I want to prove: $A_{n,1}\ge A_{n,2}\ge..\ge A_{n,r}\ge \lim_{r\to\infty} A_{n,r}=2^n$.

I can prove this for some small particular $r$ or for some small particular $n$. And checked this numerically (by computer) for a big scope of $(n,r)$.

I do not see any immediate induction or recursion. :(
(As I never learned combinatorics, the only thing I know about $S_{n,r}$ is wiki-page.) Probably this is some well known property? Any advice, reference is welcome.

share|cite|improve this question
up vote 6 down vote accepted

($A_{n,r}$ has a combinatorial interpretation: the denominator is the number of ways of partitioning the numbers $\{1,\ldots,n+r\}$ into $r$ blocks, where the list of blocks is ordered but the numbers within each block are unordered, and the numerator is the same count, except that the numbers within each block are now also ordered. $A_{n,r}$ is therefore the expected number of ways to order the numbers within each block, given a random partition of $\{1,\ldots,n+r\}$ into $r$ unordered blocks.)

Here is a proof of $A_{n,r}\ge A_{n,r+1}$: Algebraic manipulation simplifies this inequality into $$S_{n+r+1,r+1} r(r+1)\ge S_{n+r,r} (n+r)(n+r+1),$$ or, setting $m:=n+r$, $$S_{m+1,r+1} r(r+1)\ge S_{m,r} m(m+1).$$ If we multiply by $x^m/(m+1)!$ and sum over $m$, we see that it will do to prove $$r(r+1) \sum_m S_{m+1,r+1} \frac{x^{m}}{(m+1)!}\succ \sum_m S_{m,r} \frac{x^m}{(m-1)!},$$ where $\succ$ means that the inequality holds on the coefficients of each power of $x$. This can be rewritten as $$x^{-1} r(r+1) \sum_m S_{m+1,r+1} \frac{x^{m+1}}{(m+1)!}\succ x \partial_x \sum_m S_{m,r} \frac{x^m}{m!}.$$ The egf for $S_{m,r}$ in the first variable is $$\sum_m S_{m,r} \frac{x^m}{m!}=\frac{(e^x-1)^r}{r!},$$ so this becomes $$x^{-1} \frac{(e^x-1)^{r+1}}{(r-1)!}\succ x e^x \frac{(e^x-1)^{r-1}}{(r-1)!},$$ which will follow if $$(e^x-1)^2 \succ x^2 e^x.$$ This last coefficientwise inequality is true because the coefficient of $x^n$ ($n\ge 2$) is $(2^n-2)/n!$ on the left-hand side and $1/(n-2)!=n(n-1)/n!$ on the right-hand side, and $2^n-2\ge n(n-1)$ for $n\ge 2$.

share|cite|improve this answer
Doesn't the combinatorial interpretation make it obvious that the limit as r goes to infinity will be 2^n? For large r, the number of ordered partitions where all boxes are of size 1 or 2 will outnumber the number of other partitions by at least a factor of r over a constant depending on n... – zeb Sep 14 '11 at 6:47
Thanks! I'm very much impressed – Dmitry Kerner Sep 16 '11 at 2:09
One related question. I am trying to identify the function whose Taylor series is $\sum_{n\ge0}\frac{S_{n,r}t^n}{(n+r)!}\sum_{\substack{k_1,..,k_r\ge0\\k_1+\cdots‌​+k_r=n}}\prod^r_{i=1}(k_i+1)!x_i^{k_i+1}$. Again, probably this is a simple combinatorics, but I've never learned it. Any ideas about this function? Or some functions with related Taylor series? – Dmitry Kerner Sep 17 '11 at 12:17
From a combinatorial view, this function is a little odd because it mixes $r$-partitions of $\{1,\ldots,n\}$ with $r$-partitions of $\{1,\ldots,n+r\}$. I don't think it will come out to be anything simple. If you changed $S_{n,r}$ to $S_{n+r,r}$, split it up, and pushed it forward through the second sum, you would get something simple: – David Moews Sep 20 '11 at 0:17
\begin{eqnarray*} &\ &\sum_{n\ge 0} \frac{t^n}{(n+r)!} \sum_{k_1+\cdots+k_r=n} \frac{1}{r!} \binom{n+r}{k_1+1 \cdots k_r+1} \prod_{i=1}^r (k_i+1)! x_i^{k_i+1}\\ &= &\frac{1}{r!} \frac{x_1}{1-x_1t}\cdots \frac{x_r}{1-x_rt}. \end{eqnarray*} – David Moews Sep 20 '11 at 0:20

Your Answer


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.