Combinations with Replacement Calculator

Background.

Combinations with replacement, also known as multisets or multichoose, count the number of ways to select k items from a set of n distinct types when repetition is allowed and order does not matter. The canonical example is choosing k scoops of ice cream from n flavors, where multiple scoops may be the same flavor and the order in which they are placed in the cone is irrelevant. The calculator evaluates the binomial coefficient C(n+k−1, k), which gives the exact count for any non-negative integers n and k. This combinatorial concept appears in statistical mechanics, where bosons can occupy the same quantum state, in manufacturing, where a parts bin may contain multiple identical units, and in computer science, where password-strength estimators must account for repeated characters. A quality engineer sampling with replacement from a lot of n defect types needs to know how many distinct samples of size k are possible. A data scientist generating synthetic datasets with k features drawn from n categorical levels must enumerate the possible feature vectors. In each case, the standard combination formula C(n, k) is insufficient because it forbids repetition.

The formula C(n+k−1, k) = (n+k−1)! / (k!(n−1)!) can be understood through the stars-and-bars argument. Imagine k identical stars representing the selected items and n−1 bars dividing the stars into n categories. Each arrangement of stars and bars corresponds to exactly one combination with replacement. The total number of symbols is n+k−1, and choosing which k positions are stars (or equivalently which n−1 are bars) yields the binomial coefficient. This bijective proof, attributed to early twentieth-century combinatorialists and formalized in modern textbooks, is elegant because it reduces a counting problem with repetition to a counting problem without repetition.

In probability theory, combinations with replacement govern the multivariate hypergeometric distribution and its approximations. When drawing k balls from an urn containing n colors with replacement, the number of distinct color-count vectors is C(n+k−1, k). This denominator appears in Bayesian nonparametrics when enumerating partitions and in occupancy problems when distributing indistinguishable balls into distinguishable bins. The calculator therefore serves statisticians, physicists, and operations researchers who need exact counts for enumeration or normalization constants.

The computational challenge is factorial overflow. For n = 100 and k = 50, the result is C(149, 50) ≈ 2.04 × 10⁴³, which exceeds the range of 64-bit integers. The calculator uses IEEE-754 double-precision floating point, which can represent integers exactly up to 2⁵³ and approximates larger values with about 15 significant digits. For exact integer results beyond this range, arbitrary-precision libraries are required, but the double-precision output is sufficient for most practical estimation and verification tasks. The validation rules reject negative inputs and non-integer values because the combinatorial definition applies only to non-negative integers.

In software engineering, combinations with replacement model the state space of certain search algorithms. A constraint-satisfaction problem with k variables and n values per variable has n^k ordered assignments, but only C(n+k−1, k) unordered multisets if the values are indistinguishable except by type. This reduction factor guides complexity analysis and heuristics selection. In genetics, multinomial sampling with replacement describes the distribution of k offspring across n alleles under neutral drift. The normalization constant of the multinomial probability mass function involves factorials that the calculator can verify independently. The formula thus bridges recreational mathematics—how many ways to make change for a dollar using k coins of n denominations—with frontier research in algorithmic biology.

What is combinations with replacement calculator?

A combination with replacement is a selection of k objects from n distinct categories such that each category may be chosen multiple times and the order of selection is irrelevant. The result is a multiset: a generalization of a set that allows repeated elements. The notation for the count is ((n choose k)) or C(n+k−1, k), read as "n multichoose k." This quantity is also the number of weak compositions of k into n parts, where each part is a non-negative integer representing how many times a particular category was selected. The relationship to ordinary combinations is direct. Ordinary combinations C(n, k) count selections without replacement: once an item is chosen, it cannot be chosen again. Combinations with replacement relax this restriction. For example, choosing two letters from {A, B, C} without replacement yields {A,B}, {A,C}, and {B,C}: three combinations. With replacement, the selections {A,A}, {B,B}, and {C,C} are also valid, giving six total. The formula C(3+2−1, 2) = C(4, 2) = 6 confirms this enumeration. The inputs n and k must be non-negative integers. By convention, C(n, 0) = 1 for all n ≥ 1, reflecting the single empty selection. The calculator requires n > 0 and k ≥ 0. It enforces integer inputs because fractional or negative selections have no combinatorial meaning.

How to use this calculator.

1. 01Enter the set size n, which is the number of distinct categories or types available.
2. 02Enter the selection size k, which is the number of items to choose.
3. 03Ensure both n and k are non-negative integers. Decimal or negative values will be rejected.
4. 04Click the Calculate button to evaluate the multiset coefficient.
5. 05Review the Combinations with Replacement output for the exact count of possible multisets.
6. 06Check the Binomial Coefficient output to see the equivalent C(n+k−1, k) form.
7. 07Use the result to verify textbook problems, plan sampling schemes, or estimate state-space sizes.

The formula.

The standard formula for combinations with replacement is C(n+k−1, k) = (n+k−1)! / (k! × (n−1)!). This expression is a binomial coefficient evaluated at n+k−1 and k, and it can be derived rigorously via the stars-and-bars correspondence. Consider k indistinguishable stars and n−1 distinguishable bars arranged in a line of n+k−1 positions. The bars partition the line into n bins, one for each category. The number of stars in bin i represents how many times category i was selected. Because stars are identical and bars are identical within their own type, every distinct arrangement corresponds to exactly one combination with replacement, and every combination with replacement corresponds to exactly one arrangement. The number of arrangements is the number of ways to choose k positions for the stars out of n+k−1 total positions, which is C(n+k−1, k). Equivalently, one may choose n−1 positions for the bars, yielding C(n+k−1, n−1); the two binomial coefficients are equal by the symmetry identity C(m, r) = C(m, m−r). Computationally, direct factorial evaluation is inefficient and prone to overflow. The calculator should implement the multiplicative formula: C(n+k−1, k) = Πᵢ₌₁ᵏ (n+k−i) / i. This product computes the result iteratively, keeping intermediate values as small as possible and avoiding factorials entirely. At each step, the current numerator term is divided by i before multiplication, which reduces rounding error in floating-point arithmetic. The product has exactly k terms. When k > n+k−1−k = n−1, it is more efficient to compute C(n+k−1, n−1) instead, using the smaller of the two choices. The formula satisfies several identities that serve as sanity checks. Pascal's identity extends to multisets: C(n+k−1, k) = C(n+k−2, k) + C(n+k−2, k−1). The boundary conditions are C(n−1, 0) = 1 and C(n+k−1, 1) = n. For n = 1, the formula reduces to C(k, k) = 1, confirming that there is exactly one way to choose k items from a single category. For k = 0, it reduces to C(n−1, 0) = 1, confirming the empty selection.

A worked example.

Frequently asked questions.

References& sources.

1. [1]Knuth, D.E. (1997). The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Addison-Wesley. Section 1.2.6.
2. [2]Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. Wiley. Chapter II.
3. [3]Rosen, K.H. (2019). Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill. Chapter 6.
4. [4]Stanley, R.P. (1997). Enumerative Combinatorics, Vol. 1. Cambridge University Press. Section 1.2.
5. [5]NIST Digital Library of Mathematical Functions. "Binomial Coefficients." https://dlmf.nist.gov/26.3