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.


($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$.

  • 1
    $\begingroup$ 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... $\endgroup$
    – zeb
    Sep 14 '11 at 6:47
  • $\begingroup$ 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? $\endgroup$ Sep 17 '11 at 12:17
  • $\begingroup$ 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: $\endgroup$ Sep 20 '11 at 0:17
  • $\begingroup$ \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*} $\endgroup$ Sep 20 '11 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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