Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
3  
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
1  
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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.