Permutations and combinations

The formula

n! = n·(n−1)·(n−2)· ... ·2·1        0! = 1

Reading: the number of ways to line up n distinct items. The empty arrangement counts as one way, which is why 0! = 1 and not zero.

P(n,k) = n!/(n−k)! = n·(n−1)· ... ·(n−k+1)

Reading: nPr — ordered selections of k items from n, no repeats. First slot has n choices, next has n−1, and you stop after k slots. P(10,3) = 720.

C(n,k) = n!/(k!·(n−k)!) = P(n,k)/k!

Reading: nCr, "n choose k" — unordered selections ^[1]. Same count as P(n,k), then divide out the k! orderings of each group you no longer care about. C(10,3) = 120.

ordered, repeats allowed:    n^k
unordered, repeats allowed:  C(n+k−1, k)

Reading: the other two cells of the grid. A 4-digit "combination" lock is 10⁴ — it's ordered with repetition, so it's actually a permutation lock. Three scoops from four flavors, doubles allowed, is C(6,3) = 20.

C(n,k) = C(n,n−k)        C(n,k) = C(n−1,k−1) + C(n−1,k)

Reading: choosing k to keep is the same as choosing n−k to leave behind ^[1]; and each triangle entry is the sum of the two above it — Pascal's rule, which is how you build the table without touching a factorial.

Where you meet it

Sizing the test matrix. Eight configuration parameters at three levels each is 3⁸ = 6,561 full-factorial runs — nobody's test stand schedule survives that. Pairwise coverage reframes it: there are only C(8,2) = 28 parameter pairs, 9 level-combinations each, 252 pairs to cover, and a well-built matrix covers them in a few dozen runs. The counting is what turns "test everything" into a plan the program will actually fund.
The failure-combination question at the review board. FMEA and fault-tree reviews walk single failures, then someone asks about dual failures. With 40 LRUs that's C(40,2) = 780 pairs; triples jump to C(40,3) = 9,880. Combinations, not permutations — pump-then-valve and valve-then-pump are the same broken vehicle. That growth curve is the honest answer to why the analysis stops at two.
Channel hookup on the DAS. Sixteen unkeyed cables into sixteen channels can be mated 16! ≈ 2.1×10¹³ ways, exactly one of them right. That number is the whole engineering case for keyed connectors, unique cable labels, and a pre-test continuity ring-out — you are not going to luck into the correct permutation.
Frequency and channel assignment. Picking a 5-channel hop set from 50 available frequencies is C(50,5) = 2,118,760 candidate sets before interference constraints prune them. The count tells you whether exhaustive search is viable (here, trivially) or whether you need a smarter allocator.

How it works

Every counting problem reduces to two questions: does order matter, and can items repeat? That's a 2×2 grid — permutation or combination, with or without repetition — and the four formulas above fill it. Most counting mistakes are answering one of those two questions wrong, not botching arithmetic. The classic: calling a selection problem a permutation and overcounting by exactly k!, which then understates every "at least one failure" probability built on it.

The bridge to probability is the binomial coefficient. If each of n independent units fails with probability p, the chance that exactly k of them fail is C(n,k)·p^k·(1−p)^(n−k) — the C(n,k) counts which units, the powers weight one such outcome. This is why nCr sits inside every redundancy calculation: a 2-out-of-3 voting system with 0.9-reliable channels survives with probability 3·(0.9)²·(0.1) + (0.9)³ = 0.972. The conversion from counts to probabilities assumes the outcomes you counted are equally likely and independent; common-cause failures violate that assumption, and no amount of counting fixes it.

Growth is the operational hazard. Factorials outrun any exponential: 12! is the last factorial that fits a 32-bit integer, 20! the last in 64-bit, and 170! the last below double-precision overflow ^[2]. So never compute C(n,k) as three factorials — C(100,10) ≈ 1.73×10¹³ fits comfortably in a 64-bit integer even though 100! (about 9.3×10¹⁵⁷) overflows any 64-bit integer by nearly 140 orders of magnitude. Multiply and divide incrementally (result = result·(n−k+i)/i for i = 1..k), use Pascal's rule, or work with lgamma in log space. For quick mental sizing, Stirling's approximation n! ≈ √(2πn)·(n/e)^n — from a 1729 Stirling–de Moivre exchange ^[2] — lands within about 1% at n = 10 (3,598,696 versus 3,628,800) and gets better from there.

Two symmetries save real work. C(n,k) = C(n,n−k) means choosing the 47 channels you don't use is the same count as choosing the 3 you do — always compute the small side. And Pascal's rule builds the whole table with additions only, which is why lookup tables beat factorial formulas in flight software and anywhere else you don't trust intermediate overflow.

The limit of validity is distinctness. All four formulas assume distinguishable items; identical items need the multinomial correction (arrangements of MISSISSIPPI: 11!/(4!·4!·2!·1!) = 34,650, not 11!). And counting configurations is not the same as testing them — the number tells you the size of the space, not which corner of it hides the failure.

History

The subject started with poets, not gamblers. Pingala's Sanskrit prosody treatise (around the 2nd century BC) counted the meters you can build from long and short syllables — binomial coefficients in everything but name — and his 10th-century commentator Halayudha arranged the counts into the triangle Western readers call Pascal's ^[3]^[4]. Bhaskara II folded general choice-counting problems into the Lilavati in 12th-century India ^[3]^[5], and in 1321 Levi ben Gerson, a rabbi-mathematician in southern France, wrote down closed formulas for permutations and combinations, proving them with one of the earliest recorded uses of induction ^[3]^[6]. The triangle itself kept getting rediscovered — al-Karaji around 1000, Omar Khayyam, Jia Xian and Yang Hui in China ^[3]^[4].

What changed in the summer of 1654 was the application. The Chevalier de Méré, a gambler with good instincts and bad arithmetic, put the "problem of points" — how to split the pot in an interrupted game — to Blaise Pascal, and Pascal worked it out across five letters with Pierre de Fermat ^[7]^[8]. Pascal's division of the stakes ran on binomial coefficients from his arithmetical triangle ^[8]; his treatise on it, written that same year, only saw print posthumously in 1665 ^[4]^[9]. Jacob Bernoulli then did the systematizing: his Ars Conjectandi, published in Basel in 1713, eight years after his death, built probability on a worked-out theory of permutations and combinations and gave the first combinatorial (non-inductive) proof of the binomial expansion ^[10]^[11]. The notation arrived last — Christian Kramp introduced n! in his 1808 arithmetic text, crediting his colleague Arbogast for the word "factorial" ^[12]^[2].

Related tools

/tools/battery-config — series/parallel cell arrangements are a counting problem before they're an electrical one
/tools/resistor-e-series — picking from a discrete standard-value set is selection-with-constraints in the wild
/tools/bearing-life-l10 — the reliability statistics that k-of-n failure counting feeds

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →