Number of surjections
Jelly, 5 4 bytes

ṗṬML


This is an O(kn) brute force solution.

Try it online!

How it works

ṗṬML  Main link. Left argument: k. Right argument: n.

ṗ     Cartesian power; yield the list of all n-tuples over {1, ..., k}.
      Each tuple represents a (not necessarily surjective) function from
      {1, ..., n} to {1, ..., k}.
 Ṭ    Apply the "untruth" atom to each tuple.
      Ṭ maps a list of indices to an array with 1's at those indices, and exactly
      as many zeroes as needed to build the array.
      Examples:
           [1, 2, 3, 3, 3] -&gt; [1, 1, 1]
           [1, 3, 5]       -&gt; [1, 0, 1, 0, 1]
           [2, 6, 2, 4, 4] -&gt; [0, 1, 0, 1, 0, 1]
  M   Yield all indices of maximal elements, i.e., all indices of [1] * k.
   L  Take the length.