Number of combinations with repetitions with maximum different number per combination Given numbers from $1$ to $n$, how many combinations with repetitions are there to create $k$-multisets of them, with the restriction to have a maximum of $d$ different numbers in each multiset? I imagine this being a subset of all combinations with repetitions. I'm specifically referring to combinations as the order inside the multiset does not matter, e.g. $\{1,2,3\}$ is not a different combination than $\{2,1,3\}$.
Also, what would be a strategic way to generate such $k$-multisets?
Some examples with $n=3$, $k=4$, $d=2$:
Allowed:


*

*$\{1,1,1,1\}$

*$\{1,1,1,2\}$ which would be the same as $\{1,1,2,1\}$ etc.

*$\{1,3,3,3\}$ which would be the same as $\{3,1,3,3\}$ etc.


Not allowed:


*

*$\{1,1,1\}$ not a $k$-multiset

*$\{1,2,3,3\}$ more than $d$ different numbers

 A: To avoid double-counting let us count the sets with exactly $d$ distinct elements. This means that any of $d$ elements is present in multiset at least once. Observe that the multisets differ only by the counts of the elements. Taking into account that the count of each element is at least one the overall number of the corresponding multisets is essentially the number of way to distribute the rest $k-d$ elements into $d$ "bins", which by stars and bars is:
$$
\binom{k-d+d-1}{k-d}=\binom{k-1}{d-1}
$$
The overall number of such multisets is:
$$
N_{nkd}=\binom nd\binom{k-1}{d-1},
$$
where $\binom{n}d$ is the number of ways to choose $d$ elements out of $n$.
Finally the number of all multisets with number of distinct element not exceeding $d$ is:
$$
N^*_{nkd}=\sum_{i=1}^d\binom ni\binom{k-1}{i-1}.
$$
A: Hint:
You can work by knowing the numbers that you choose. For example, if $d=2$ then call $A_i=\text{# of k-tuples with exactly i distinct numbers}.$

So you solution would be 
$$\sum _{i=1}^dA_i.$$
Now, to compute $A_i,$ pick the $i-$elements that you want to use. Say in $\binom{n}{i}$ ways. Now, we can say that if $x_j$ is the number of times the $j-$th element appears in the set of the $i$ that you chose then you will have to have that $x_j\geq 1$ and that $x_1+\cdots +x_i=k$ because there are $k$ elements at the end. Can you finish?
