Number of surjections Task

Given 2 positive integers n and k, where n &gt; k, output the number of surjections from a set of n distinguishable elements to a set of k distinguishable elements.

Definition

A function f: S → T is called a surjection if for every t∈T there is s∈S such that f(s) = t.

Example

When n=3 and k=2, the output is 6, since there are 6 surjections from {1,2,3} to {1,2}:


1↦1, 2↦1, 3↦2
1↦1, 2↦2, 3↦1
1↦1, 2↦2, 3↦2
1↦2, 2↦1, 3↦1
1↦2, 2↦1, 3↦2
1↦2, 2↦2, 3↦1


Testcases

n k output
5 3 150
8 4 40824
9 8 1451520


Reference


OEIS A019538


Scoring

This is code-golf. Shortest answer in bytes wins.

Standard loopholes apply.
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.