1
$\begingroup$

A famous and simple lower bounds for Stirling numbers of the second kind is as follows:

$$\binom{n}{k-1} \le {n\brace k}$$

I tried to prove that using the relation $${n\brace k}=\frac{1}{k!}\sum_{j=0}^{k}\binom{k}{j}\left(-1\right)^{j}\left(k-j\right)^n$$

But could not conclude the result.Is it possible to prove this lower bound without using induction? ( If yes then please provide the proof, if no then use induction).

Also why we the lower bound does hold for this example: $$4=\binom{4}{3}+\binom{5}{3}\color{red}{\nleq}{4\brace 4}+{5\brace 4}=1$$

Improve this question
$\endgroup$
  • $\begingroup$ Unless I am mistaken, ${4\brace 4}+{5\brace 4} = 1 + 10 = 11$ $\endgroup$ – Martin R Mar 20 '20 at 10:39
  • 1
    $\begingroup$ Does this answer your question? A property of Stirling Numbers of the Second kind (Combinatorics related) $\endgroup$ – Martin R Mar 20 '20 at 10:42
  • 1
    $\begingroup$ @ Martin R,but is not ${n\brace n-1}=\binom{n}{2}$? $\endgroup$ – user715522 Mar 20 '20 at 10:43
  • 1
    $\begingroup$ @ Martin R , the link does not provide a proof without using induction) $\endgroup$ – user715522 Mar 20 '20 at 10:44
  • $\begingroup$ $\binom{n}{k-1} \le {n\brace k}$ is apparently wrong for $k=n > 1$. $\endgroup$ – Martin R Mar 20 '20 at 10:54
0
$\begingroup$

Suppose $k<n,$ consider a partition like $$\pi =\{B_1,\cdots, B_{k-1},B_k\},$$ such that $B_i=\{a_i\}$ and $1\leq a_1<a_1<\cdots <a_{k-1}\leq n,$ and $B_k=[n]\setminus \{a_1,\cdots ,a_{k-1}\}$ if $k<n,$ then $|B_k|>1$ so it is clear that this way produces an inclusion of $\binom{n}{k-1}$ in the partitions of $[n]$ into $k$ blocks, and the inequality is satisfied.

The problem with $k=n$ is that you are counting a lot of times($n$ times) the same partition(mainly $1/2/\cdots /n$).

Improve this answer
$\endgroup$
  • $\begingroup$ @ Phicar,what does the left hand side tell us? $\endgroup$ – user771003 May 22 '20 at 8:42
  • $\begingroup$ @user715522 It tells us the number of partitions of this form that i wrote down. But because they are not all the partitions possible, then the inequality holds. Unless, clearly, if $n=k.$ $\endgroup$ – Phicar May 22 '20 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy