let S(m,n)denote the number of onto functions from a set with m elements to a set with n elements. show that S(m,n) satisfies the recurrence relation

S(m,n)= n^{m} - sum_{k=1}^{n-1}C(n,k)S(m,k)
whenever m=n and n1, with initial condition S(m,1)=1.

Question

let S(m,n)denote the number of onto functions from a set with m elements to a set with n elements. show that S(m,n) satisfies the recurrence relation

S(m,n)= n^{m} - sum_{k=1}^{n-1}C(n,k)S(m,k)
whenever m>=n and n>1, with initial condition S(m,1)=1.

anonymous · Answer

$$s(m,n)= n^{m} - \sum_{k=1}^{n-1}C(n,k)s(m,k)$$