Most efficient way of computing the number of surjective functions from N to K?

[Nineshadow]

Basically we want to know in how many ways we can arrange n elements from a set of k elements such that every element is included at least once. Let's take as an example n=3, and k=2, with the set K={1,2}. There are 6 possible arrangements : {1,1,2},{1,2,1},{2,1,1},{1,2,2},{2,1,2},{2,2,1}.

Now, I've realized that the number I'm looking for is equal to k!*S(n,k), where S is the Stirling number of the 2nd kind,  since I'm permuting k elements, and the partitions are equal to partitions of n elements into a non-empty subset of k elements. But now I'm not really sure how I should go about computing it.

 

First of all, there's a recurrence relation for the Stirling numbers. That is, S(n,k)=S(n-1,k-1)+k*S(n-1,k). Calculating this is pretty straight forward, then there's only the factorial left to do.

 

Still, after some research I've also found the explicit formula for the Stirling number of the 2nd kind, which is :

Which would be another way of doing things, but probably in a slower way than before.

 

So, which should I use? Recurrence or the explicit formula? Or some other way?

[Nineshadow]

Another thought:

Let T(n,k)=k!*S(n,k)

 

If S(n,k)=S(n-1,k-1)+k*S(n-1,k), then

k!*S(n,k)=k!*S(n-1,k-1)+k!*k*S(n-1,k)

T(n,k)=(k-1)!*S(n-1,k-1)*k+k!*S(n-1,k)*k

So :

T(n,k)=k*(T(n-1,k-1)+ T(n-1,k) ).