Take the 2-minute tour ×

I need to prove such a formula:

$$ \left\{ \begin{matrix} n \\ k-1 \end{matrix} \right\} \cdot \left\{ \begin{matrix} n \\ k+1 \end{matrix} \right\} \le \left\{ \begin{matrix} n \\ k \end{matrix} \right\}^{2} \\ $$ Where {} are Stirling numbers of the second kind.
(number of ways to partition a set of n objects into k non-empty subsets).

I tried to figure out some combinatorial proof, but failed.

I'd be grateful for any help.

share|improve this question
What is the source of this problem? –  Aryabhata Mar 8 '12 at 21:55
A sequence $c_n$ is called discrete log-concave if $c_n^2 \geqslant c_{n-1} c_{n+1}$. This article by Sibuya proves the discrete log-concavity for Stirling numbers. –  Sasha Mar 8 '12 at 22:26
Possibly related: An Inequality Involving Bell Numbers –  Mike Spivey Mar 8 '12 at 22:34
There is a fairly short but very non-combinatorial proof in Herbert S. Wilf’s generatingfunctionology, which may be downloaded here as a hyperlinked PDF. The desired result is Corollary 4.5.3. Do you just need a proof, or do you specifically want t combinatorial proof? –  Brian M. Scott Mar 9 '12 at 8:53
Combinatorial proof was rather my personal guess. I just noticed that huge amount of Stirling-number-related formulas have clear and easy combinatorial proof, that's all. –  Maria McKee Mar 9 '12 at 11:35

Your Answer



Browse other questions tagged or ask your own question.