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$

  • $\begingroup$ A more concise formulation of the question is "How many multisets of size $k$ can be formed from a set of $n$ elements?" $\endgroup$ – AlexR Dec 18 '16 at 8:56

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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.