0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – rubikman23
    Oct 14 at 22:40
  • 1
    $\begingroup$ @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. $\endgroup$
    – Phicar
    Oct 15 at 8:50
  • $\begingroup$ 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 ! $\endgroup$
    – rubikman23
    Oct 15 at 13:05
  • 1
    $\begingroup$ @rubikman23 Precisely. Well done! $\endgroup$
    – Phicar
    Oct 15 at 13:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.