# Inequality with Stirling numbers of second kind

I have to prove that, $$\forall n\geq 1$$, $$\forall 1\leq k\leq n$$, $$\frac{k^{n}}{k^{k}}\leq S(n,k)\leq \frac{k^{n}}{k!}$$

The second inequality, is quite obvious for me, as $$k!\cdot S(n,k)$$ is the number of surjective applications from a set of $$n$$ elements to a set of $$k$$ elements ($$k^{n}$$ is the total number of applications from a set of $$n$$ elements to a set of $$k$$ elements), so, $$k!S(n,k)\leq k^{n}$$ $$\Rightarrow$$ $$S(n,k)\leq \frac{k^{n}}{k!}$$.

Nevertheless I don't really know how to approach the first inequality... Probably I could relate it again with the number of applications,... I don't really know.

A hint / some help would be so useful! Thanks in advanced!

Hint: So, what if you have a set partition where you know $$1,2,\cdots ,k$$ are in different parts. In how many ways can you assigned the other $$n-k$$ elements?
Are these all possible partitions of $$[n]$$ into $$k$$ blocks?
• Could you help me a little more? I have thinking it, and I haven't really understand what you are saying... Are you asking me to ''put'' those $n-k$ elements in the preexisting parts, and count all the posibilities? Sorry for not getting it, and thanks a lot Oct 14 at 22:40
• @rubikman23 Sure, no worries. Notice that $k^n/k^{k}=k^{n-k}$ and this are functions that go from $k+1,k+2,\cdots , n$ into $k$ elements. So I am saying that these assignments represent those partitions. Oct 15 at 8:50
• Oh, ok! So, is it this?... So, taking a set of $n$ cardinal, and labelling its elements $1,...,n$, $k^{n-k}$ counts the number of applications that go from $k+1$, $k+2$,...,$n$, to the subsets $\{1\},...,\{k\}$ (considering that, for ex., if the image of $k+1$ is $\{2\}$, we include $k+1$ in that part). So, this applications are really defining some partitions over the initial set. Nevertheless, these are not the total of partitions, as for example, any partition with $\{1,2\}$ as a part wouldn't be in the set defined by this applications. Hence, $k^{n-k}\leq S(n,k)$. Thanks a lot @Phicar ! Oct 15 at 13:05