How Many Combinations Are Possible with Limited Repetitions?

Suppose you have $n$ types of items and want to select $k$ items, with order ignored. Type $i$ may be selected no more than $a_i$ times. The selection is determined by how many items of each type you take, so the task is to count the possible count-vectors $(x_1,\ldots,x_n)$ satisfying the limits and total.

The general answer is a coefficient in a generating function. This handles different limits for different types, while a shorter inclusion-exclusion formula applies when every type has the same limit.

Model a combination as counts

Let $x_i$ be the number selected from type $i$. Then a valid combination corresponds to one integer solution of

$$x_1+x_2+\cdots+x_n=k,\qquad 0\le x_i\le a_i.$$

Because order does not matter, selecting two items of type A and one of type B is one combination, not three different arrangements. If each physical item is distinct, or if order matters, this count-vector model is not the right model without additional choices.

A necessary condition for any selection to exist is $k\le a_1+\cdots+a_n$. If this fails, the answer is zero.

Use a generating function for arbitrary limits

For type $i$, the allowed counts are $0,1,\ldots,a_i$. Encode them by the polynomial

$$1+x+x^2+\cdots+x^{a_i}.$$

Multiply these polynomials across all types. Choosing a term $x^{x_i}$ from factor $i$ records taking $x_i$ items of that type. The exponent in the product is the total number selected, so the coefficient of $x^k$ counts exactly the valid combinations:

$$\boxed{[x^k]\prod_{i=1}^{n}(1+x+x^2+\cdots+x^{a_i})}.$$

Here $[x^k]F(x)$ means “the coefficient of $x^k$ in $F(x)$.” This is often the cleanest answer when capacities differ. For a numerical calculation, multiply the polynomials while discarding terms of degree greater than $k$.

Worked example: four types, at most two of each

How many ways can you select five items from four types if each type may appear at most twice? The generating function is

$$(1+x+x^2)^4,$$

so the answer is the coefficient of $x^5$.

A direct count by the pattern of selected counts is useful as a check. The nonnegative counts must sum to 5, each at most 2. The only possible patterns are $(2,2,1,0)$ and $(2,1,1,1)$, up to rearrangement.

For $(2,2,1,0)$, choose which type appears once in $4$ ways, then choose which of the remaining three types is absent in $3$ ways. The other two types appear twice. This gives $4\cdot3=12$ combinations. For $(2,1,1,1)$, choose the type that appears twice in $4$ ways. The total is

$$12+4=16.$$

Thus there are 16 combinations.

A formula when every type has the same limit

If all $n$ types can be chosen at most $r$ times, start with the unrestricted number of nonnegative solutions to $x_1+\cdots+x_n=k$. By stars and bars, that number is $\binom{k+n-1}{n-1}$. Then use inclusion-exclusion to remove solutions in which one or more counts are at least $r+1$:

$$\boxed{\sum_{j=0}^{\lfloor k/(r+1)\rfloor}(-1)^j\binom{n}{j}\binom{k-j(r+1)+n-1}{n-1}}.$$

A binomial coefficient term is included only for feasible indices; terms with $j>n$ are omitted. Each chosen set of $j$ types is shifted down by $r+1$ selections, which explains the reduced total inside the second binomial coefficient.

For the example above, $n=4$, $r=2$, and $k=5$. The formula gives

$$\binom{8}{3}-\binom{4}{1}\binom{5}{3}=56-40=16.$$

No two types can both exceed the limit, since that would require at least six selections, so there are no further nonzero terms.

Common mistakes

• Using ordinary combinations without repetition: $\binom{n}{k}$ counts choosing $k$ distinct types, so it only applies when each type can be used at most once.
• Using unrestricted stars and bars: $\binom{k+n-1}{n-1}$ allows a type to be selected any number of times. It overcounts when there are upper limits.
• Counting arrangements instead of combinations: If order is irrelevant, do not multiply by the number of ways to arrange the selected items.
• Ignoring feasibility: If $k$ exceeds the sum of the capacities, the count is zero. If $k$ is small enough that no limit can be exceeded, the unrestricted stars-and-bars count is valid.

If each type must be selected at least once as well as at most $a_i$ times, replace its factor by $x+x^2+\cdots+x^{a_i}$, provided every $a_i\ge1$. The coefficient method then counts selections satisfying both bounds.