4
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 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
    Commented Sep 14, 2011 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$
    – Dmitry Kerner
    Commented Sep 17, 2011 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$
    – David Moews
    Commented Sep 20, 2011 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$
    – David Moews
    Commented Sep 20, 2011 at 0:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .