Combinations with Replacement Calculator

Background.

Three scoops from a counter with 31 flavors, where two or even all three scoops may be the same flavor and nobody cares which went in first: there are 5,456 different cups you could be handed. Counting them is a combinations-with-replacement problem. Mathematicians also call the result a multiset, or "31 multichoose 3", and the count is the binomial coefficient C(n + k − 1, k), here C(33, 3).

Set that beside the neighboring counts and the role of each assumption becomes clear. If the three scoops had to be different flavors, the answer would be the ordinary combination C(31, 3) = 4,495. If order mattered, so that vanilla-on-top differed from vanilla-at-the-bottom, every one of the three positions could take any of 31 flavors, giving 31³ = 29,791 sequences. Allowing repeats while ignoring order lands in between, and it is the one of the four cases that needs a trick to count. The gap between 4,495 and 5,456 is easy to account for by sorting cups by their pattern of repeats: 31 × 30 = 930 cups have two scoops of one flavor and one of another, 31 cups are a single flavor three times, and 4,495 + 930 + 31 = 5,456.

The same number answers questions that do not look like selections at all. Handing k identical items to n people, finding the non-negative whole-number solutions of x₁ + x₂ + … + xₙ = k, listing the distinct results k dice can show, and counting the terms of a polynomial of degree k in n variables are all the same count in disguise. Physics meets it too, wherever identical particles have to be shared among quantum states.

One warning belongs up front, because it catches people who move from counting to probability. The multisets are not equally likely when the items are drawn at random. Two dice can show 21 different unordered results, but a double one comes up once in 36 rolls while a one-and-two comes up twice in 36, because it can happen two ways. Dividing by the multiset count gives the wrong probability; for chance questions you count ordered outcomes instead.

What is combinations with replacement calculator?

A combination with replacement is an unordered selection of k items from n distinct types in which any type may be chosen more than once. The result is a multiset, a collection like a set except that elements can repeat, so {A, A, C} is a legitimate selection and is the same selection as {A, C, A}. Choosing 2 from the types A, B and C gives six of them: AA, AB, AC, BB, BC and CC. A multiset is fully described by how many copies of each type it holds, so the count is also the number of ways to write k as an ordered sum of n non-negative whole numbers, which combinatorics calls the weak compositions of k into n parts. The usual notation is C(n + k − 1, k), sometimes written with doubled parentheses and read "n multichoose k". It assumes an unlimited supply of every type, or at least k of each.

How to use this calculator.

1. 01Enter the number of distinct types in Set Size (n): flavors on offer, faces on a die, variables in a polynomial, or people receiving items. It is the number of kinds, not the number of physical items in stock.
2. 02Enter how many items each selection contains in Selection Size (k): scoops per cup, dice rolled, the degree of the polynomial, or identical items being handed out. Both values must be whole numbers, with n at least 1.
3. 03If every type must appear at least once, enter k − n instead of k. Placing one of each first leaves k − n items to choose freely, and the count of those free choices is the answer.
4. 04Before trusting the count, check its three assumptions: items of one type are interchangeable, order does not matter, and each type is available at least k times. If the items can be told apart, like numbered lottery balls, an ordinary combination or n to the power k is the right tool instead.
5. 05Read the count. The second output shows the same number labeled as the binomial coefficient C(n + k − 1, k), so the two always agree; a result of 10¹⁵ or more is shown in scientific notation to four significant figures.

The formula.

The count is C(n + k − 1, k) = (n + k − 1)! ÷ (k! × (n − 1)!), and the cleanest way to see why is the stars-and-bars picture. Write each selection as a row of k stars, one per item, divided into n compartments by n − 1 bars. With four types and seven items, ★★|★||★★★★ means two of the first type, one of the second, none of the third and four of the fourth. Every multiset gives exactly one such row and every row gives exactly one multiset, so counting multisets means counting rows. A row has n + k − 1 symbols, and it is fixed completely once you decide which k of those positions hold stars, which is an ordinary combination C(n + k − 1, k). Choosing the n − 1 bar positions instead gives C(n + k − 1, n − 1), the same number by the symmetry of binomial coefficients.

A second route explains the shape of the numbers. Every selection either contains none of the last type, leaving k items to choose from n − 1 types, or contains at least one, in which case removing one copy leaves k − 1 items from all n types. Adding the two cases gives a recurrence like Pascal's triangle: the count for 5 types and 8 items, 495, is the 165 selections of 8 items from 4 types plus the 330 selections of 7 items from 5 types.

The edge values follow from the formula without special rules. With k = 0 there is one selection, the empty one; with one type there is one selection, k copies of it; and with k = 1 there are n. For a fixed number of types the count grows as a polynomial in k of degree n − 1: two types give k + 1, and three give (k + 1)(k + 2) ÷ 2. The answer is computed by multiplying and dividing one factor at a time rather than through full factorials, which keeps intermediate values small; results below about 10¹⁴ come out as exact whole numbers.

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