Select $k$ items from $n$ such that every item can occur in the combination for at most $k$ times.

Question

What is the generic formula for- Select $k$ items from $n$ items such that every item can occur in the combination for at most $k$ times, e.g. Let us assume we have $n=3$ items namely $\{A,B,C\}$, of these $3$ items we have to select $k=3$ items such that any of the items can occur at most $k=3$ times. In that way the number of combination would be $10$ which are-

$AAA$, $BBB$, $CCC$, $AAB$, $ABB$, $AAC$, $ACC$, $BBC$, $BCC$, $ABC$

Answer 1

The analytical way

Let's try to find a recurrence for said number, call the number $M(n, k)$.

Trivially, if there is only $n=1$ element to chose from, there is only one possible solution:

$$M(1, k) = 1$$

and clearly for $k=0$ there is only one set, $\emptyset$:

$$M(n, 0) = 1$$

Now let's add a new element, $n$ to our set and count the multisets:

1. Chose how many times $n$ is in the multiset, call it $k_n \in \{0, \ldots, k\}$
2. From the other $n-1$ elements, build a multiset of size $k - k_n$

This means we get the recurrence $$M(n,k) = \sum_{j=0}^k M(n-1, k-j)$$

This happens so be solved by $$M(n, k) = \binom{n + k - 1}{k}$$

The combinatorial way

Imagine a number of stars, $*$ in a row, where we can put bars in between. We now want to encode a multiset of size $k$ as follows:

Place $n-1$ bars in between some stars, so that we get a division of the stars into $n$ "buckets". Since we can only place one separator into each gap, each bucket has at least one star.

To translate this to a multiset where one bucket (= element of the size $n$ set) can be empty, we must subtract one. This happens $n$ times and the number of occurences of element $a_k$ in our multiset will be the size of bucket $k$ - 1.

If we had $s$ stars in the beginning, the multiset has size $s - n$. Since $s - n = k$, we have $s = n + k$ stars and thus $s-1 = n + k - 1$ gaps to put $n - 1$ bars into:

$$M(n, k) = \binom{n + k - 1}{n - 1} = \binom{n + k - 1}{k}$$