most recent 30 from http://mathoverflow.net 2013-06-19T19:00:52Z http://mathoverflow.net/feeds/question/75369 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75369/a-bound-involving-stirling-numbers-of-the-second-kind-and-the-asymptotics Dmitry Kerner 2011-09-14T02:34:16Z 2011-09-14T05:18:07Z

<p>Let $S_{n,r}$ denote the Stirling number of the second kind. Define <code>$A_{n,r}:=\frac{\binom{n+r-1}{n}(n+r)!}{S_{n+r,r}r!}$</code>. I want to prove: <code>$A_{n,1}\ge A_{n,2}\ge..\ge A_{n,r}\ge \lim_{r\to\infty} A_{n,r}=2^n$</code>.</p> <p>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)$.</p> <p>I do not see any immediate induction or recursion. :(<br> (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.</p>

http://mathoverflow.net/questions/75369/a-bound-involving-stirling-numbers-of-the-second-kind-and-the-asymptotics/75379#75379 David Moews 2011-09-14T05:18:07Z 2011-09-14T05:18:07Z

<p>($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.)</p> <p>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$.</p>