Combinatorics answers a single recurring question in disguise: in how many ways can a set of objects be arranged or selected? The trouble is that this question hides several genuinely different sub-problems, and picking the wrong formula is almost always a sign that one of these distinctions was overlooked rather than a sign of a computational mistake. What follows untangles them by reducing every counting problem to a small number of yes/no decisions, then derives all six resulting formulas from the basic multiplication principle of counting, so that the right formula becomes something you can reconstruct rather than something you have to remember.
Throughout, the running picture is an urn containing \(n\) distinguishable balls, from which some or all balls are drawn.
Two Questions That Determine the Right Formula
Every counting problem of this kind is settled by asking, in order:
- Q1 — Arrange or select? Are all \(n\) objects being arranged, or is only a smaller number \(k\) of them being selected from the \(n\) available? Arranging everything is called a permutation; selecting \(k<n\) objects splits further via Q2 and Q3.
- Q2 — Does order matter? If two selections consisting of the same objects but drawn in a different order count as different outcomes, order matters and the count is a variation. If only the resulting set of objects counts, order does not matter and the count is a combination.
- Q3 — With or without replacement? If a ball is put back into the urn before the next draw, the same ball can appear again: this is drawing with repetition (with replacement). If drawn balls stay out, this is drawing without repetition (without replacement).
Combining these answers gives exactly six named cases, summarized here and derived one by one below:
| Name | Arrange all, or select \(k\) of \(n\)? | Order matters? | Repetition allowed? | Formula |
|---|---|---|---|---|
| Permutation without repetition | arrange all \(n\) | — | no | \(n!\) |
| Permutation with repetition | arrange all \(n\) (some identical) | — | — | \(\dfrac{n!}{k_1!\,k_2!\cdots}\) |
| Variation without repetition | select \(k\) of \(n\) | yes | no | \(\dfrac{n!}{(n-k)!}\) |
| Variation with repetition | select \(k\) of \(n\) | yes | yes | \(n^k\) |
| Combination without repetition | select \(k\) of \(n\) | no | no | \(\binom{n}{k}\) |
| Combination with repetition | select \(k\) of \(n\) | no | yes | \(\binom{n+k-1}{k}\) |
Interactive Case Finder
Answer the questions below to see which case applies and compute it for concrete numbers.
Permutation Without Repetition
Suppose all \(n\) balls are distinguishable and every one of them is placed into a row. The first position can be filled by any of the \(n\) balls. Once that choice is made, the second position can be filled by any of the remaining \(n-1\) balls, the third by any of the remaining \(n-2\), and so on until the last position, for which only \(1\) ball is left. By the multiplication principle, the total number of orderings is the product of these counts:
\[n\cdot(n-1)\cdot(n-2)\cdots 2\cdot 1=n!\]
This is a permutation without repetition: every arrangement of \(n\) distinguishable objects, with none left out and none repeated.
Example. An urn holds six differently colored balls. Arranged in a row, they admit
\[6!=1\cdot2\cdot3\cdot4\cdot5\cdot6=720\]
different orderings.
Variation Without Repetition: Selecting With Order, No Replacement
Now only \(k\) of the \(n\) balls are drawn, one at a time, without putting any of them back, and the order in which they come out is recorded. The same counting argument as above still applies, except that it stops after \(k\) positions instead of continuing to the last ball: \(n\) choices for the first draw, \(n-1\) for the second, down to \(n-k+1\) for the \(k\)-th. Multiplying these \(k\) factors gives
\[n\cdot(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!},\]
since multiplying and dividing by \((n-k)!\) turns the truncated product back into a ratio of full factorials. This count is called a variation without repetition. It reduces to plain permutation without repetition when \(k=n\), since \((n-n)!=0!=1\).
Some textbooks call this same quantity a \(k\)-permutation of \(n\) instead of a variation; both names refer to exactly the count \(\frac{n!}{(n-k)!}\), so encountering either term should not cause confusion about which formula applies.
Example. From the same box of six balls, four are drawn without replacement and lined up in the order drawn:
\[\frac{n!}{(n-k)!}=\frac{6!}{(6-4)!}=\frac{6!}{2!}=\frac{720}{2}=360\]
ordered outcomes.
Combination Without Repetition: Selecting Without Order, No Replacement
If instead only which \(k\) balls came out matters, not the order they were drawn in, every group of \(k\) balls has been counted once for each of the \(k!\) ways its members could have been ordered among themselves. Dividing the variation count by this overcounting factor gives the number of unordered selections:
\[\binom{n}{k}:=\frac{1}{k!}\cdot\frac{n!}{(n-k)!}=\frac{n!}{k!\,(n-k)!}.\]
This is the binomial coefficient, read “\(n\) choose \(k\)”, and the count it gives is called a combination without repetition. Its structure becomes transparent when read starting from the permutation of all \(n\) balls: the numerator \(n!\) arranges every ball; the denominator then collapses two orderings that a plain selection does not distinguish, namely the internal order of the \(k\) chosen balls and the internal order of the \(n-k\) balls left behind:
\[ \binom{n}{k} = \frac{ \overbrace{n!}^{\text{all orderings of all }n\text{ balls}} }{ \underbrace{k!}_{\text{orderings within the chosen }k} \cdot \underbrace{(n-k)!}_{\text{orderings within the remaining }n-k} } \]
Example. A lottery draws \(6\) numbers out of \(49\), with the order of the draw irrelevant to the outcome:
\[\binom{n}{k}=\binom{49}{6}=13{,}983{,}816.\]
Almost \(14\) million equally likely tickets exist, which is the combinatorial fact behind how unlikely a lottery win is.
Two Useful Facts About Binomial Coefficients
Two structural properties of \(\binom{n}{k}\) are worth knowing beyond its defining formula. First, it is exactly the coefficient of \(x^k\) in the expansion of \((1+x)^n\), since expanding the product of \(n\) copies of \((1+x)\) picks, for each term, either the \(1\) or the \(x\) from each factor, and the number of ways to pick \(x\) from exactly \(k\) of the \(n\) factors is precisely the number of \(k\)-element selections out of \(n\):
\[(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k.\]
Second, this generating-function view immediately yields Pascal's rule. Comparing the coefficient of \(x^{k+1}\) on both sides of the identity \((1+x)^{n+1}=(1+x)^n(1+x)\) — where the right side contributes to that coefficient either by taking \(x^{k+1}\) from \((1+x)^n\) and \(1\) from the extra factor, or \(x^k\) from \((1+x)^n\) and \(x\) from the extra factor — gives
\[\binom{n}{k+1}+\binom{n}{k}=\binom{n+1}{k+1}.\]
This is exactly the recurrence that generates Pascal's triangle row by row.
Finally, since factorials of even moderately large \(n\) are unwieldy to compute exactly, Stirling's approximation gives a fast estimate:
\[n!\approx n^n e^{-n}\sqrt{2\pi n}.\]
Permutation With Repetition: Arranging a Multiset
A different situation arises when the \(n\) objects being arranged are not all distinguishable: say \(k_1\) of them are identical copies of type \(1\), \(k_2\) are identical copies of type \(2\), and so on, with \(k_1+k_2+\cdots=n\). Swapping two identical balls produces the same physical row, so plain \(n!\) overcounts every distinct-looking arrangement once for each way its same-colored balls could be permuted among themselves.
This count is reached most transparently as a chain of combinations without repetition: first choose which \(k_1\) of the \(n\) positions hold type \(1\), in \(\binom{n}{k_1}\) ways; then, among the remaining \(n-k_1\) positions, choose which \(k_2\) hold type \(2\), in \(\binom{n-k_1}{k_2}\) ways; and so on. Multiplying these choices together,
\[ \binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\cdots = \frac{n!}{k_1!\,(n-k_1)!}\cdot\frac{(n-k_1)!}{k_2!\,(n-k_1-k_2)!}\cdot\frac{(n-k_1-k_2)!}{k_3!\,(n-k_1-k_2-k_3)!}\cdots \]
every intermediate factorial cancels against the next factor's numerator, leaving
\[\frac{n!}{k_1!\,k_2!\,k_3!\cdots}.\]
This is the count of a permutation with repetition, also called a multiset permutation.
Example. An urn contains three green and two yellow balls, five in total. Their distinguishable arrangements in a row number
\[\frac{n!}{k_1!\,k_2!}=\frac{5!}{3!\,2!}=\frac{120}{12}=10.\]
Variation With Repetition: Selecting With Order, With Replacement
Returning to selecting \(k\) balls out of \(n\), now suppose each drawn ball is put back before the next draw and the order of the draws is recorded. Every one of the \(k\) draws again has all \(n\) balls available, independently of what was drawn before, so the multiplication principle gives
\[\underbrace{n\cdot n\cdots n}_{k\text{ times}}=n^k.\]
This is a variation with repetition. Note that the “permutation of all \(n\) objects” viewpoint used for the two “without repetition” cases above does not apply here: with replacement, the same ball can occupy several positions at once, so the outcomes are no longer a subset of the arrangements of a fixed collection of \(n\) distinct balls, and the count has to be built directly from the multiplication principle instead.
Example. Four balls are drawn from the box of six, each replaced before the next draw, and the sequence of colors is recorded:
\[n^k=6^4=1296\]
possible sequences.
Combination With Repetition: Selecting Without Order, With Replacement
The last case selects \(k\) balls with replacement, as above, but only records how many balls of each color were drawn, not the order. Such an outcome is fully described by a tuple of counts \((c_1,\ldots,c_n)\), one per color, with every \(c_i\ge 0\) and \(c_1+\cdots+c_n=k\).
Counting these tuples is a classical bijection known as stars and bars: write the \(k\) drawn balls as \(k\) identical stars, and separate the count for color \(1\) from color \(2\), color \(2\) from color \(3\), and so on, using \(n-1\) bars. A row such as
\[\star\star\,|\,\star\,|\,\,|\,\star\star\star\]
(for \(n=4\) colors) encodes the tuple \((2,1,0,3)\): two stars before the first bar, one between the first and second bar, none between the second and third, and three after the last bar. Every such row consists of exactly \(k\) stars and \(n-1\) bars, that is, \(n+k-1\) symbols in total, and every tuple corresponds to exactly one arrangement of these symbols, obtained by choosing which \(k\) of the \(n+k-1\) positions hold stars (the rest are bars automatically):
\[\binom{n+k-1}{k}.\]
This is a combination with repetition.
Example. Three balls are drawn with replacement from the box of six colors, and only the resulting color counts matter:
\[\binom{n+k-1}{k}=\binom{6+3-1}{3}=\binom{8}{3}=56.\]
A Common Pitfall: Two Different Meanings of “With Repetition”
Both permutation with repetition and variation with repetition contain the phrase “with repetition”, but they count fundamentally different things, and conflating them is one of the most frequent sources of error in this topic:
- Permutation with repetition starts from a single, fixed collection of \(n\) objects that already contains repeats (such as \(3\) green and \(2\) yellow balls) and asks for the number of distinguishable ways to arrange all of them. The formula \(\frac{n!}{k_1!k_2!\cdots}\) removes overcounting caused by identical objects.
- Variation with repetition starts from \(n\) distinct object types and asks for the number of ordered sequences of length \(k\) built by repeatedly choosing with replacement from all \(n\) types. The formula \(n^k\) counts independent repeated choices, not arrangements of a fixed multiset.
The safest way to tell them apart is Q1 from the very first section: permutation always arranges every given object exactly once, repeated or not, while variation and combination select only \(k\) out of a larger pool of \(n\), possibly reusing pool elements when repetition is allowed.
Key Results
- Every counting problem is settled by three questions: arrange everything or select \(k\) of \(n\); if selecting, does order matter; and is repetition (replacement) allowed.
- Permutation without repetition: \(n!\), arranging all \(n\) distinguishable objects.
- Permutation with repetition: \(\frac{n!}{k_1!k_2!\cdots}\), arranging all \(n\) objects of a multiset with group sizes \(k_1,k_2,\ldots\), derivable as a telescoping chain of combinations.
- Variation without repetition: \(\frac{n!}{(n-k)!}\), ordered selection of \(k\) from \(n\) without replacement; also called a \(k\)-permutation.
- Variation with repetition: \(n^k\), ordered selection of \(k\) from \(n\) with replacement.
- Combination without repetition: \(\binom{n}{k}=\frac{n!}{k!(n-k)!}\), unordered selection of \(k\) from \(n\) without replacement; also the coefficient of \(x^k\) in \((1+x)^n\) and subject to Pascal's rule \(\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}\).
- Combination with repetition: \(\binom{n+k-1}{k}\), unordered selection of \(k\) from \(n\) with replacement, proved by the stars-and-bars bijection.
- Permutation with repetition and variation with repetition both contain the words “with repetition” but answer different questions: one arranges a fixed multiset, the other makes repeated independent choices.