Let's compress your set of values to a representation like S = [1:2, 2:1, 3:2]
where you just save the value and the count for every element and assign them some order. Let n be the size of the sequence S. You then have 2^count possibilities to select a subset for every value.
For every group you have to decide whether to take it or not. If you take it, the number of distinct values increases and you have 2^count - 1 possibilities to do so. If not, the number of distinct values stays the same.
This yields the following DP approach: Let f(i, k) be the number of ways to make decisions from index i on, given that you are only allowed to use k more distinct values.
The recurrence is
f(n, k) = 1 if k >= 0
f(n, k) = 0 if k < 0
f(i, k) = f(i + 1, k) + (2^count[i] - 1) * f(i + 1, k - 1)
Leading to an O(n * k) algorithm. The result will be f(0, k).