Number of bags of a given length with exactly d distinct elements

2026-08-14

We develop a formula for counting the number of bags of length \(l\) containing \(d\) distinct elements drawn from \(t\) objects. The formula involves multiplication of combinations without replacement and combinations with replacement. We present alternative forms of the formula and a generator in Python. Our motivation was computing probabilities of various types of card hands, such as how many hands of size 5 contain exactly two suites.

Introduction

In games, a matching mechanic may be used to restrict a player’s choice to options that match a previous play. Trick-taking games, a popular and specialized subset of matching, often restrict a player to “follow” a previous play’s cards suites or colors. In computer science, a function may assign items to specific buckets (e.g. a hash function) and we are concerned with the spread and number of collisions with a bucket. For analyzing both types of problems we likely desire to count the total number of variations possible.

In our case, we were modeling collections of cards drawn from a deck using a variation of the Python code below.

def distinct_generator(d: int, l: int, t: int):
    assert d > 0 and l > 0 and t > 0, "all must be positive integers"
    assert l >= d and t >= d, "l and t must be greater than or equal to d"
    for bag in itertools.combinations_with_replacement(range(0, t), l):
        actual_d = len(set(bag))
        if actual_d == d:
            yield seq

A note on novelty We wrote this article to document a formula since we could not find prior art to reference. However, combinatorics is a well-studied area, so we expect textbooks may include this a student problem.

Number of bags

A bag is an unordered collection that may contain duplicates. A bag is also called a multiset. Bags differ from a set, which is also unordered but may not contain duplicates, and a sequence, which is ordered and can contain duplicates.

Let \(d\) be the number of distinct element within a bag, \(l\) be the total size or length of a bag, and \(t\) be the number of discrete elements from which we populate bags. All three variables are positive integers.

Theorem 1 The number of bags of length \(l\) with \(d\) discrete elements drawn from \(t\) possible elements, where \(d\), \(l\), \(t\) are all positive integers, \(t \geq d\), and \(l \geq d\) is:

$$ \begin{equation} N(d, l, t) = \binom{t}{d} \binom{l-1}{l-d} \end{equation} $$

Notationally, the parentheses expression is the binomial coefficient.

Aside Equation 1 can also be written as:

$$ N(d, l, t) = \binom{t}{d} \binom{l - 1}{d - 1} $$

This form may be more convenient computationally. The equivalence of the two equations is given by Lemma 1.

Lemma 1 The expression \(\binom{l-1}{l-d} = \binom{l-1}{d-1}\). We can demonstrate the equivalency through first showing the identity \(\binom{n}{k} = \binom{n}{n-k}\):

$$ \binom{n}{k} \stackrel{?}{=} \binom{n}{n-k} $$

$$ \frac{n!}{k!(n-k)!} \stackrel{?}{=} \frac{n!}{(n-k)!(n - n + k)!} $$

$$ \frac{n!}{k!(n-k)!} = \frac{n!}{k!(n-k)!} $$

Using this identity, \(\binom{l-1}{l-d} = \binom{l-1}{d-1}\) can be shown algebraically.

Strategy

Conceptually, we first generate all bags with \(d\) distinct elements from \(t\). Each bag will have length \(d\). Then, for each of these original bags, we generate pads. Each pad is a bag with size \(l-d\) and is restricted to the \(d\) elements in the original, although as a bag these elements may be duplicated. The total number of bags is equal to the number of original bags multiplied by the number of padded bags (or one, if the pads have zero length.)

For example, if there are three types of cards (\(t=3\)), a hand size of five (\(l=5\)), and we restrict to two distinct card types per hand (\(d=2\)), then as shown in the table below, there are three original bags, each with four pads of length 3 (\(l-d\)). The third column shows the original appended with each pad, rewritten into lexicographic order since the order of the hand does not matter. There are 12 total bags as a result.

As proof of the equation, we will first discuss the first term and generation of the original bags, and then discuss the second term and generation of the pads.

Original Bags

We generate the original bags by drawing \(d\) unordered elements from \(t\) possibilities. This is the definition of a combination and is computed as \(\binom{t}{d}\). With \(d=l\), the second term \(\binom{l-1}{l-d}\) becomes \(\binom{l-1}{0}\) which simplies to 1, so if there are no pads, the formula is still valid.

Pads

Pads are generated differently than the original bags because they can contain duplicate items. The order of items still does not matter, so this is an example of combinations with replacement or multichoose. Let \(e\) be the size of the individual pads and \(e = l - d\). We are generating \(e\) objects from the \(d\) variants in the corresponding original bag, so by definition (and including translating multichoose to equivalent binomial representation):

$$ \bigg(\negthinspace\negthinspace\binom{d}{e}\negthinspace\negthinspace\bigg) = \binom{d + e -1 }{e} $$

Replacing \(e\) with \(l - d\), we obtain \(\binom{l-1}{l-d}\).

Appendix: Computed Results

This table contains computed results for \(d\) values between 2 and 5, \(l\) values between d and 10, and \(t\) values between d and 10. All ranges are inclusive.