Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

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|cite|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


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.