My own progress:
The total number of possible outcomes is N to the power of k. To find the number of favorable outcomes I think you should consider permutations on a multiset. The number of permutations on a multiset is given by the multinomial coefficient:
k! / (z_1! z_2! ... z_i! ... z_z!),
where k is the length of the multiset (and therefore k! is the number of permutations if there were no duplicates) and z_i is the number of times the i-th distinct element occurs.
Using this multinomial coefficient, however, requires figuring out the number of duplicates to plug into the multinomial coefficient (i.e. the z_i's) . You know that if there are z distinct values you need to draw and if you have to draw k values that k-z values will have to be duplicates. However, many different cases arise. For instance one of the z values might have all the duplicates or the duplicates might be spread more equally among the z values. Taking this into account is hard.