2
$\begingroup$

Prove that, for all integers $n \gt 1$, $$n! \lt S(2n,n) \lt (2n)!,$$ where $S(n.k)$ denotes the Stirling numbers is the number of ways of placing $n$ distinct balls into $k$ identical boxes so that no box remains empty.

I have got the second inequality i.e. $S(2n,n) \lt (2n)!$.

Here's the proof. Suppose $A$ is a set such that $\# A=2n$, and we have partitioned $A$ into $n$ subsets such as $\{a_,,a_2,\dots, a_{n_1}\},\{b_1,b_2,\dots,b_{n_2}\},\dots$, and we have chosen the elements in the order such as $a_1\lt a_2\lt \dots\lt a_{n_1}\lt b_1\lt b_2\lt\dots\lt b_{n_1}\lt \dots$. We can associate this with a permutation $P$ such that $P(a_1)=a_2,P(a_2)=a_3,\dots, P(a_{n_1})=a_1; P(b_1)=b_2,P(b_2)=b_3,\dots,P(b_{n_2})=b_1,\dots$

So not all permutations of $A$ correspond to this kind of partitions, but all this partitions correspond to some kind of permutation of $A$. So, number of partitions is less than the number of permutations.

So,$$S(2n,n)\lt (2n)!,$$ not only this, by this argument, we easily get that $$\sum_{i=1}^n S(2n,n)\lt (2n)! $$

But, how shall I show that $S(2n,n)\gt n!$?

I would like any combinatorial proof. I also tried to prove this using strong induction, but got stuck.

And most important query, $$\Large{\text{Is there any “proofs without words" for this question?}}$$

$\endgroup$
1
$\begingroup$

Put the balls numbered $1$ through $n$ in one box each, and the balls numbered $n+1$ through $2n$ in one box each. This defines a permutation of the numbers $n+1$ through $2n$, of which there are $n!$.

$\endgroup$

Your Answer

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