5
$\begingroup$

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.

  • 0
    What is the source of this problem?2012-03-08
  • 3
    A sequence $c_n$ is called discrete log-concave if $c_n^2 \geqslant c_{n-1} c_{n+1}$. This [article](http://www.ism.ac.jp/editsec/aism/pdf/040_4_0693.pdf) by Sibuya proves the discrete log-concavity for Stirling numbers.2012-03-08
  • 1
    Possibly related: [An Inequality Involving Bell Numbers](http://math.stackexchange.com/q/67988/2370)2012-03-08
  • 0
    There is a fairly short but very non-combinatorial proof in Herbert S. Wilf’s *generatingfunctionology*, which may be downloaded [here](http://www.math.upenn.edu/~wilf/DownldGF.html) 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?2012-03-09
  • 0
    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.2012-03-09

0 Answers 0