Generally, knowing how to sum a_n and b_n separately doesn't lead to a nice formula for the sum of (a*b)_n. Sometimes summation by parts is helpful, sometimes not.
Can we find meaning in the expression? n^(k) counts the number of functions that map a k-element set to an n-element set. k is the size of the domain and n-k is the max size of the complement of the range (the set of elements each function doesn't hit). But because the functions are not generally bijective, that is all we can say about the range.
If we knew the functions were bijective, then there would be a nice relationship with combinations, but alas.
In what context did this arise?