Confirming the correctness of Combinatoric permutation formula

Question

for the ordering and distinguishable non-empty, is it $$ (n)k = n(n-1)(n-2)\cdots(n-k+1) $$ for no ordering distinguishable non-empty, i got $$ \sum_{i=0}^{n-1}(-1)^i\dbinom{n}{i}(n-i)^k $$

please ignore Catalan numbers, I have got the answer already.

Thanks!

Answer 1

You should look at the Twelvefold Way of Gian-Carlo Rota. It discusses 12 common counting problems - see how yours fit in.

A good reference for this is Enumerative Combinatorics, Volume 1 by R. P. Stanley (Section 1.4 in the second edition). Also, it is Stirling numbers.