Counting arrangements, counting selections, and the factorial that separates them.
Overview
The question to ask first
Does order matter?
Three medals from eight runners: gold, silver and bronze are different outcomes based on who gets which. So Order matters. That is a permutation.
Three people for a committee from eight: the same three people are the same committee but you list them. Order doesn't matter. That is a combination.
All else follows from answering that.
Combinatorics: Permutations and Combinations
This module needs JavaScript: the
numbers are computed in the page rather than recorded.
Worth knowing
Permutations count arrangements — order matters. n! / (n−k)!
Combinations count selections — order does not. n! / (k!(n−k)!)
The two differ by exactly k!: the number of orders each selection could have arrived in.
The bars are C(n, k) for every k. Symmetric, because choosing k to keep is choosing n−k to leave.
Combinatorics: Permutations and Combinations
The counting that chance is built on. The one question that decides which formula to use.
The formulas
Permutations of k from n:
P(n, k) = n! / (n - k)!
There are n choices for the first spot, n - 1 for the second, and so on for k spots. The factorial ratio is just that product written compactly.
Combinations of k from n:
C(n, k) = n! / ( k! (n - k)! )
Count the sorted setups, then divide by k! because each unordered pick was counted once for each order its members could have appeared in.
The readout makes the tie concrete: at n = 12, k = 5 the sorted count is 95,040 and the unordered is 792. 95,040 / 792 is just 120 = 5!.
Reading the shape
The bars are C(n, k) for each k from 0 to n.
Even.C(n, k) = C(n, n-k). Choosing which k to keep is the same act as choosing which n - k to leave.
Largest in the middle. There are far more ways to pick half of a thing than to pick almost none or almost all.
Huge quickly. Drag n to 24 and the middle bar passes two and a half million. This growth is why brute force over subsets is hopeless past small n, and why the readout switches to scientific form.
That row of numbers is a row of Pascal's triangle, and the recurrence C(n,k) = C(n-1,k-1) + C(n-1,k). Either the last item is in your pick or it isn't — is the standard dynamic-programming way to find them without factorials.
With repetition
A third case, easy to miss. If the same item can be chosen more than once and order matters — a 4-digit PIN. Here Digits may repeat — the count is simply n^k. The readout gives this alongside.
At n = 10, k = 4 that is 10,000 PINs, against P(10, 4) = 5,040 if no digit could repeat.
Why it matters here
Binomial chances. The C(n, k) in the binomial is just this count — the number of orders in which k successes could have arrived.
Hypothesis testing. Permutation tests build a null spread by enumerating or sampling rearrangements of the labels, and the count above says whether enumeration is feasible.
Cross-validation. The number of ways to split data into folds.
Feature pick. Choosing k features from n is C(n, k), which is why exhaustive search is abandoned almost right away and greedy or smoothed methods are used instead.
cost args. A great deal of "this is exponential" is this table growing.
Where it goes wrong with Combinatorics
Not asking whether order matters. The commonest error, and it's a factor of k!.
finding factorials right.21! overflows a 64-bit int, and C(n, k) is often far smaller than the factorials used to define it. Work in logarithms, or use the multiplicative recurrence. This Is what this page does.
Losing repetition is allowed. Passwords, dice and sampling with swap all permit it.
Double counting. When the objects aren't all distinguishable the plain formulas over-count, and the multiset versions are needed instead.
A worked example: the birthday problem
In a room of 23 people, the chance that two share a birthday is just over half. That number is famous for feeling wrong, and working it out teaches the single most handy counting trick there's.
Counting "at least one shared birthday" right is miserable: one pair, two pairs, a triple, a triple and a pair. So on, all shared. So count the opposite — all birthdays different — which is one clean product, and subtract from 1. This is complementary counting, and reaching for it's often the whole trouble of a counting problem.
With 365 equally likely days and k people, the total number of ways to assign birthdays is 365^k. The number of ways with no repeat is P(365, k), the sorted count from above. So:
Each new person must dodge each birthday already taken, so each factor is slightly smaller than the last:
people
P(all different)
P(a shared birthday)
10
0.883
11.7%
20
0.589
41.1%
23
0.493
50.7%
30
0.294
70.6%
50
0.030
97.0%
70
0.0008
99.9%
The reason 23 feels far too small is that people picture *their own* birthday being matched, which needs 253 people to reach even odds. The question is not about you. It's about pairs, and 23 people make C(23, 2) = 253 of them. Each a separate chance to collide.
That gap between "people" and "pairs" is a quadratic hiding behind a linear intuition, and it's just why hash collisions arrive far sooner than the table size suggests. The birthday bound is the reason a 64-bit hash starts colliding after around 2³² items rather than 2&sup4;.
Questions people ask about Combinatorics
Which of the three formulas do I want? Two questions settle it each time — can an item repeat, and does order matter:
repeats?
order matters?
count
example
yes
yes
n^k
a 4-digit PIN
no
yes
P(n, k)
gold, silver, bronze
no
no
C(n, k)
a committee of three
yes
no
C(n+k-1, k)
scoops of ice cream
How do I find C(n, k) without overflowing? Never build the factorials. Times and divide alternately — C(n,k) = C(n,k-1) * (n-k+1) / k — which keeps each mid an exact int and roughly the size of the answer. For very large n, work with lgamma in log space and exponentiate at the end. Python's math.comb already does the safe thing.
Why is C(n, 0) equal to 1? There's just one way to choose nothing: take nothing. It isn't a special case bolted on. It's what makes the symmetry C(n,k) = C(n,n-k) and Pascal's recurrence hold at the edges without exceptions.
What if some items are the same? The plain formulas assume each item is distinguishable. Arranging the letters of *BANANA* isn't 6!, because swapping the two Ns changes nothing. Divide by the factorial of each repeat count, 6!/(3! 2! 1!) = 60.
Is C(n, k) the same as "n choose k"? Yes. And the same as the binomial coeff, and the same as a row entry of Pascal's triangle. Three names, one number, which is a large part of why this topic reads as harder than it's.
List them, then count them
Small enough to print each setup. So The formulas are checkable rather than stored.
example_01.pyNumPy
import math
from itertools import permutations, combinations
items = "ABCD"
print("permutations of ABCD taken 2 at a time (order matters):")
perm = list(permutations(items, 2))
print(" ", ["".join(p) for p in perm])
print(" count %d = 4!/(4-2)! = %d" % (len(perm), math.perm(4, 2)))
print()
print("combinations of ABCD taken 2 at a time (order does not):")
comb = list(combinations(items, 2))
print(" ", ["".join(c) for c in comb])
print(" count %d = 4!/(2!*2!) = %d" % (len(comb), math.comb(4, 2)))
print()
print("every combination collapses 2! = 2 permutations:")
print(" %d / %d = %d" % (len(perm), math.factorial(2), len(comb)))
print()
print("this is why the numbers explode:")
for n in (5, 10, 20, 52):
print(" %2d items: %d orderings, %d hands of 3"
% (n, math.factorial(n), math.comb(n, 3)))
Output
Check yourself
0 of 3
Answer without scrolling back up.
What separates a permutation count from a combination count?
At n = 12, k = 5 the ordered count is 95,040 and the unordered is 792, and the ratio is exactly 120 = 5!.
Why is C(n, k) symmetric in k?
The same partition of the set, described from either side - which is why the bars mirror around the middle.
Why should you not compute C(n, k) from factorials directly?
Work in logarithms or use the multiplicative recurrence. Pascal's identity C(n,k) = C(n-1,k-1) + C(n-1,k) is the standard dynamic-programming route.
Cheat sheet
Combinatorics: Permutations and Combinations
Count arrangements with and without order, with and without replacement. One decision tree picks the right formula every time.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.