Combinations with Repetition

How many ways can you choose a dozen donuts from five varieties? This simple question introduces a powerful mathematical concept: combinations with repetition. Unlike simple combinations, here we can select the same item multiple times, and unlike permutations, the order of selection doesn't matter. This seemingly niche counting problem appears in the most unexpected places, forming a hidden thread that connects genetics, quantum mechanics, and even the laws of spacetime. This article demystifies this fundamental principle. In the "Principles and Mechanisms" section, we will introduce the elegant "stars and bars" method and the abstract power of generating functions. Following this, the "Applications and Interdisciplinary Connections" section will reveal how this single idea is applied to count everything from genetic possibilities and particle states to the fundamental components of physical laws.

In our journey of scientific discovery, we often find that the most profound ideas are born from the simplest of questions. The concept we are about to explore is no different. It begins with a question you might ask at a bakery: "How many ways can I choose a dozen donuts if there are five varieties available?" You don't care about the order they are placed in the box; you only care about the final tally—three glazed, four chocolate, one strawberry, and four plain, for instance. This seemingly mundane question of choosing items where repetition is allowed and order is irrelevant opens the door to a surprisingly powerful principle that echoes through genetics, quantum physics, and even the description of spacetime itself.

Before we dive in, let's sharpen our focus. Imagine you are a system administrator monitoring jobs being assigned to one of three servers, $S_1, S_2, S_3$. If two jobs arrive, the sequence of assignments matters. An outcome of $(S_1, S_2)$ (first job to $S_1$, second to $S_2$) is different from $(S_2, S_1)$. To list all possibilities, we must consider every ordered pair, leading to $3 \times 3 = 9$ unique outcomes. This is a problem of ​​ordered selections with repetition​​.

But what if you are the editor of a scientific journal who only receives an aggregate tally of votes from a panel of four referees? Each referee can vote "Accept," "Revise," or "Reject." The editor doesn't see the individual votes like (Accept, Reject, Accept, Revise); they only see the final count, such as (2 Accepts, 1 Revise, 1 Reject). The individual referees are now like indistinguishable votes being placed into distinct categories. The order is gone, and we are left with a simple tally. How many different tallies are possible? This is the heart of our new question, a problem of ​​combinations with repetition​​.

To solve this kind of problem, mathematicians and physicists use a beautifully simple visual device known as ​​stars and bars​​. Let's tackle the referee problem. We have $n=4$ votes (our "items") to distribute among $k=3$ categories ("bins").

Imagine the four votes as four stars in a row:

$\star \star \star \star$

Now, to divide these stars into three categories (Accept, Revise, Reject), we need to place $k-1 = 2$ dividers, or "bars," among them. For example, the arrangement:

$\star \star | \star | \star$

could represent 2 "Accepts", 1 "Revise", and 1 "Reject". What if all four votes were "Accept"? That would look like:

$\star \star \star \star | |$

Here, we have four stars before the first bar (4 Accepts), no stars between the two bars (0 Revises), and no stars after the second bar (0 Rejects).

Every possible voting tally corresponds to a unique arrangement of these 4 stars and 2 bars. The problem has been transformed! Instead of thinking about votes and categories, we are now just arranging a sequence of 6 symbols (4 stars and 2 bars). The total number of positions in our sequence is $n + (k-1) = 4 + 2 = 6$. To find the number of unique arrangements, we just need to choose which of these 6 positions will be occupied by the 2 bars. The rest will automatically be filled with stars.

The number of ways to do this is given by the binomial coefficient:

$\binom{\text{total positions}}{\text{positions to choose}} = \binom{n+k-1}{k-1} = \binom{4+3-1}{3-1} = \binom{6}{2}$

Calculating this gives us $\frac{6 \times 5}{2 \times 1} = 15$. There are 15 possible distinct tallies the editor could receive. This elegant method gives us a general formula for any problem of this type. The number of ways to choose $n$ items from $k$ categories with repetition allowed is:

$\binom{n+k-1}{n} \quad \text{or equivalently,} \quad \binom{n+k-1}{k-1}$

This single formula, born from a simple visual trick, is the key that unlocks a surprising number of doors in the natural world.

The true beauty of a fundamental principle is its universality. The "stars and bars" logic isn't just a mathematical curiosity; it's a pattern woven into the fabric of reality.

The Blueprint of Life

Consider the field of genetics. A diploid organism, like a human, has two copies of each autosomal (non-sex) chromosome. Suppose a particular gene on one of these chromosomes comes in three different versions, or ​​alleles​​: $A_1$, $A_2$, and $A_3$. The organism's genotype for this gene consists of the pair of alleles it possesses. Since the two chromosomes are functionally equivalent for this purpose, the order doesn't matter; a genotype of $(A_1, A_2)$ is identical to $(A_2, A_1)$. An individual can also have two copies of the same allele, like $(A_1, A_1)$.

How many possible genotypes are there? We are choosing $n=2$ alleles to form the genotype, from a pool of $k=3$ available allele types. Repetition is allowed (homozygous case), and order doesn't matter (heterozygous case). This is our problem in disguise! Using the formula:

$\text{Number of genotypes} = \binom{n+k-1}{n} = \binom{2+3-1}{2} = \binom{4}{2} = 6$

There are exactly 6 possible genotypes. The simple act of counting donut combinations finds its parallel in the fundamental mechanism of heredity. This logic can be extended to more complex scenarios, such as genes on sex chromosomes, to map out the entire landscape of possible genetic diversity in a population.

The Social Life of Particles

Perhaps the most profound appearance of this principle is in quantum mechanics. The universe is built of particles, and these particles come in two fundamental families: ​​fermions​​ (like electrons) and ​​bosons​​ (like photons, the particles of light). A key difference between them is how they behave in groups. The Pauli Exclusion Principle states that no two identical fermions can occupy the same quantum state. Bosons, however, are more sociable; any number of identical bosons can pile into the same state.

Furthermore, identical quantum particles are truly, perfectly indistinguishable. If you have two bosons in two different states, it is physically meaningless to ask which boson is in which state. The only thing that has physical reality is the ​​occupation number​​: the count of how many particles are in each available state.

Imagine a simple system with $n=2$ identical bosons and $k=4$ distinct single-particle states they can occupy. To describe a possible configuration of the system, we don't label the bosons; we just list how many of them are in each of the 4 states. This is exactly the stars-and-bars problem. The two bosons are the "stars," and the four quantum states are the "bins." The number of distinct two-boson states is:

$\text{Dimension of Hilbert Space} = \binom{n+k-1}{n} = \binom{2+4-1}{2} = \binom{5}{2} = 10$

This number, 10, is a fundamental property of the system—the dimension of its state space. This combinatorial rule dictates everything from the properties of lasers (which rely on many bosons occupying the same state) to the behavior of liquid helium. The same logic allows us to enumerate all possible energy states of a system of bosons and calculate macroscopic properties like its total energy.

The Shape of Physical Laws

The pattern appears again when we describe the physical properties of materials or even the structure of spacetime. In physics, many properties are described by ​​tensors​​, which are mathematical objects that generalize scalars and vectors. For example, in an anisotropic crystal, the dielectric permittivity tensor, $\epsilon_{ij}$, relates the electric field to the material's response. In a 3-dimensional space, this rank-2 tensor could have up to $3 \times 3 = 9$ components.

However, fundamental physical principles often impose symmetries. For the dielectric tensor, energy conservation demands that it be symmetric, meaning $\epsilon_{ij} = \epsilon_{ji}$. This means the component for the (row 1, column 2) direction is the same as for (row 2, column 1). The pair of indices $\{i, j\}$ is unordered. To count the number of independent components we need to measure, we are choosing 2 indices from $d$ dimensions, where repetition is allowed (for diagonal elements like $\epsilon_{11}$) and order doesn't matter. For a $d$-dimensional space, this is:

$\text{Independent Components} = \binom{d+2-1}{2} = \binom{d+1}{2} = \frac{d(d+1)}{2}$

This same logic extends to higher-rank tensors. A completely symmetric rank-3 tensor $S_{ijk}$ in $d$ dimensions, used in theories like general relativity, has a number of independent components given by choosing 3 indices from $d$ with repetition:

$\text{Independent Components} = \binom{d+3-1}{3} = \binom{d+2}{3} = \frac{d(d+1)(d+2)}{6}$

What began as a way to count donuts ends up quantifying the essential complexity of our physical laws.

The distinction between choosing with and without replacement is critical, and nowhere is this clearer than in modern statistics. Consider a researcher testing a drug on five patients. The observed recovery times are $\{5, 6, 7, 8, 12\}$. Two patients were in the treatment group and three in the control.

To perform a ​​permutation test​​, we assume the drug has no effect. This means the five recovery times are a fixed set of numbers, and any assignment of them to the two groups was equally likely. The total number of ways to partition these five distinct numbers is to choose which 2 go into the treatment group. This is sampling without replacement. The number of possibilities is:

$N_P = \binom{5}{2} = 10$

Now, consider a different method: a ​​bootstrap test​​. Here, we might pool all five numbers and create a new "pseudo-group" by drawing a sample of size 3 with replacement. Because we sample with replacement, we could draw the number '7' three times, creating a sample of $\{7, 7, 7\}$. The order in which we draw them doesn't matter, only the final multiset. This is combinations with repetition. We are choosing $n=3$ items from $k=5$ types of numbers.

$N_B = \binom{n+k-1}{n} = \binom{3+5-1}{3} = \binom{7}{3} = 35$

The two procedures, built on subtly different assumptions about sampling, lead to vastly different numbers of possible outcomes. Understanding combinations with repetition is not just an academic exercise; it is essential for correctly applying and interpreting modern statistical methods.

There is another, more abstract and powerful way to view this entire subject: through the lens of ​​generating functions​​. Instead of manipulating stars and bars, we can encode our counting problem into a polynomial.

Let's say we want to pick items from $k$ categories. For a single category, the choice is "pick 0 items," "pick 1 item," "pick 2 items," and so on. We can represent this choice with a formal power series: $1 + x + x^2 + x^3 + \dots$. The exponent of $x$ represents the number of items we pick from that category.

To get the total number of choices across all $k$ categories, we multiply the series for each category together:

$(1 + x + x^2 + \dots) \times (1 + x + x^2 + \dots) \times \dots \times (1 + x + x^2 + \dots) \quad (k \text{ times})$

This is equal to $(1 + x + x^2 + \dots)^k$. Each of these infinite sums is a geometric series, which we know sums to $\frac{1}{1-x}$. So our generating function is simply:

$G(x) = \left(\frac{1}{1-x}\right)^k = (1-x)^{-k}$

The magic is this: when you expand this function back into a power series, $\sum c_n x^n$, the coefficient $c_n$ of the $x^n$ term automatically counts the number of ways to pick a total of $n$ items from the $k$ categories! It does this because, in multiplying the polynomials, each way of forming an $x^n$ term corresponds to picking $x^{y_1}$ from the first series, $x^{y_2}$ from the second, and so on, such that $y_1 + y_2 + \dots + y_k = n$.

Using a tool called the Generalized Binomial Theorem, we can find the coefficients of this expansion. And what do we find?

$c_n = \binom{n+k-1}{n}$

We have arrived at the very same stars-and-bars formula, but from a completely different direction, by manipulating algebraic expressions. This beautiful convergence of combinatorics and algebra reveals a deeper structure to the problem. Generating functions are a cornerstone of modern combinatorics, providing a powerful engine for solving a vast array of counting problems, often in a way that feels like magic.

From a simple choice at a bakery to the structure of matter and spacetime, the principle of combinations with repetition demonstrates the remarkable unity of scientific thought—a single, elegant idea recurring across the intellectual landscape.

You might not think that the proteins busily working in your cells, the genetics governing the color of a tropical fish, and the very fabric of spacetime described by Einstein have much in common. At first glance, they seem to inhabit entirely different worlds. But Nature, in her beautiful economy, often relies on the same fundamental patterns to build complexity from simplicity. One of the most surprisingly universal of these patterns is a simple counting rule: the number of ways to choose items from a set when you're allowed to pick the same item more than once. This is the idea of ​​combinations with repetition​​, and once you learn to recognize it, you'll start seeing it everywhere. It's like having a special pair of glasses that reveals a hidden layer of order connecting disparate fields of science.

Let's begin our journey in the world of biology, where this principle is a matter of life and inheritance.

Consider the vibrant Blue-lipped Cichlid, a fish whose scale coloration is a marvel of genetic diversity. Suppose geneticists discover that this coloration is controlled by a single gene that exists in 7 different versions, or alleles, within the population. Since the cichlid is a diploid organism, like us, its genotype for this gene consists of a pair of alleles, one inherited from each parent. How many different genotypes are possible? An individual could be homozygous, having two copies of the same allele (like $A_1A_1$ or $A_2A_2$), or heterozygous, with two different alleles (like $A_1A_2$). Because the combination $A_1A_2$ is biologically identical to $A_2A_1$, the order doesn't matter. This is precisely a problem of choosing 2 alleles from a set of 7, with repetition allowed. The solution is not $7 \times 7$, but a more subtle count that tallies all the unique pairs, revealing the full spectrum of genetic possibility for this trait.

This same logic scales from whole organisms down to the molecular machinery inside our cells. Proteins are the workhorses of the cell, and many function as multi-part complexes, or oligomers, built from smaller polypeptide subunits. A classic example is the enzyme Lactate Dehydrogenase (LDH), which is crucial for energy production. It functions as a tetramer, meaning it's made of four subunits. In vertebrates, these subunits come in two principal types: 'M' (for muscle) and 'H' (for heart). A functional LDH enzyme can be formed from any combination of these four subunits. How many different types of LDH, or isozymes, can exist? We need to form a group of 4 subunits by choosing from the 2 available types ('M' and 'H'), with repetition. The possible compositions range from purely M-type ($M_4$) and purely H-type ($H_4$) to all the mixed versions in between ($H_3M_1$, $H_2M_2$, $H_1M_3$). Our counting principle elegantly reveals there are exactly five distinct isozymes, each with slightly different properties tailored to the tissues in which they are found.

The principle further orchestrates the flow of information in cellular signaling. The JAK-STAT pathway is a critical communication system that relays signals from outside the cell to the nucleus to control which genes are turned on or off. When a signal arrives, specific STAT proteins are activated. These activated proteins must then pair up, forming dimers, to do their job. If, for instance, a signal activates two types of STAT proteins, say STAT1 and STAT3, what are the possible messengers that can be sent to the nucleus? The cell can form STAT1-STAT1 homodimers, STAT3-STAT3 homodimers, or STAT1-STAT3 heterodimers. Again, we are choosing a pair of items from a set of two, with repetition allowed. This combinatorial step is a key source of diversity in biological signaling; by activating different combinations of STAT proteins, a cell can generate a wide array of distinct regulatory outputs from a limited toolkit of components, allowing for exquisitely specific responses to different stimuli.

Let's now switch our perspective from the ordered world of biology to the teeming, chaotic world of atoms and energy. In statistical mechanics, we seek to understand the macroscopic properties of matter—like temperature and pressure—from the microscopic behavior of its constituent particles. A central concept is that of a microstate, which is a specific arrangement of particles and energy.

Imagine a simplified model of a solid, represented by an array of $N$ tiny, identical quantum oscillators. Suppose we inject a total of $q$ discrete packets of energy, or quanta, into this system. How many ways can this energy be distributed among the oscillators? This is the quintessential "stars and bars" problem, a visual representation of combinations with repetition. The number of ways to distribute $q$ identical quanta among $N$ distinct oscillators is the same as the number of ways to choose $q$ items from a set of $N$ (the oscillators), where we are allowed to give multiple quanta to the same oscillator. This calculation isn't just an academic exercise; it's the foundation for deriving the statistical definition of entropy, a measure of disorder, and underpins our understanding of heat and thermodynamics from first principles.

The same combinatorial challenge appears with a vengeance in quantum chemistry. Calculating the properties of a molecule requires solving the Schrödinger equation, a task complicated by the mutual repulsion between every pair of electrons. In computational methods like the Hartree-Fock approximation, these interactions are calculated as two-electron repulsion integrals (ERIs). For a molecule described by $K$ basis functions (which represent the orbitals), a single integral involves four such functions: $(\mu\nu|\lambda\sigma)$. Naively, this suggests we might have to calculate $K^4$ integrals, a number that becomes astronomically large very quickly.

However, due to fundamental symmetries, most of these integrals are duplicates. For example, $(\mu\nu|\lambda\sigma)$ is the same as $(\nu\mu|\lambda\sigma)$ because the order of functions in the pair doesn't matter. It is also the same as $(\lambda\sigma|\mu\nu)$ because the two electrons are indistinguishable. The problem of counting the unique integrals that must be calculated reduces to a clever, two-step application of combinations with repetition. First, one counts the number of unique pairs of orbitals like $(\mu\nu)$. Then, one counts the number of ways to choose two of these pairs to form the integral. Recognizing this structure reduces the computational burden by a huge factor, making calculations that would otherwise be impossible, tractable.

Having seen this principle at work in living systems and quantum clouds, we can now ascend to a higher level of abstraction and see it as a fundamental feature of the mathematical language used to describe the universe. In physics and engineering, many quantities are represented by tensors—mathematical objects that generalize vectors and matrices.

A simple yet profound example comes from Einstein's theory of general relativity, where the geometry of spacetime is described by a symmetric tensor. The Ricci tensor, $R_{\mu\nu}$, is a key object in Einstein's field equations. It's a rank-2 tensor in $N$-dimensional spacetime (for us, $N=4$), meaning it looks like an $N \times N$ matrix. The crucial property is its symmetry: $R_{\mu\nu} = R_{\nu\mu}$. This means the component in row $\mu$, column $\nu$ is the same as the one in row $\nu$, column $\mu$. How many independent numbers do we actually need to define this tensor? We are choosing two indices, $\mu$ and $\nu$, from the set of $N$ possible dimensions. Since the tensor is symmetric, the order of the indices doesn't matter, and since we can have diagonal components like $R_{\mu\mu}$, repetition is allowed. The problem of counting the independent components of a symmetric tensor is, yet again, our familiar counting problem.

This idea generalizes with beautiful elegance. What if a hypothetical physical theory involved a completely symmetric rank-3 tensor, $T^{\mu\nu\sigma}$, in 4-dimensional spacetime? The symmetry here means the components are unchanged by any reordering of the three indices. The number of independent components is the number of ways to choose 3 indices from a set of 4, with repetition. What about a completely symmetric rank-5 tensor on a 4-dimensional space? It's the number of ways to choose 5 indices from a set of 4, with repetition. The same formula, $\binom{n+k-1}{n}$, which we found in genetics and quantum statistics, provides the answer instantly. This reveals the concept not just as a counting trick, but as a deep truth about the structure of symmetric multilinear objects.

This abstract principle finds surprisingly concrete applications in modern technology. A major challenge in fields from control engineering to econometrics is creating accurate mathematical models of complex, nonlinear systems. A powerful tool for this is the Volterra series, which describes a system's output as a function of its current and past inputs.

To capture nonlinearity, the model includes not just the inputs themselves ($x[n], x[n-1], \dots$) but also products of inputs, like $x[n]x[n-1]$ or $x[n-2]^2$. These products are called monomials. An engineer building such a model needs to know: for a given model complexity (say, up to products of degree $P$) and memory (looking back $M$ steps in time), how many distinct terms are there to account for? Counting the number of unique input monomials of a certain degree is mathematically identical to counting the number of unique components of a symmetric tensor, or distributing quanta among oscillators. It is, once more, a problem of combinations with repetition. Understanding this combinatorial explosion is vital for designing efficient algorithms to identify the parameters of the model from experimental data. It allows engineers to manage the complexity and computational cost of modeling sophisticated real-world systems.

From the building blocks of life to the structure of spacetime and the design of modern control systems, the simple act of choosing with repetition emerges as a unifying thread. It is a testament to the fact that the universe, for all its complexity, is governed by principles of remarkable simplicity and scope. The real joy of science is in discovering these threads and watching as they weave together the disparate patches of our knowledge into a single, coherent, and beautiful tapestry.