Combinatorics: The Formulas for Counting Possibilities

According to the Treccani Enciclopedia della Matematica, combinatorics deals with counting possibilities: how many arrangements, how many choices, how many orderings a set of elements can produce, without needing to list them one at a time. Underneath sits the multiplication principle: when a first choice has a certain number of outcomes and a second, independent choice has another, the combined outcomes come from multiplying the two numbers. That same logic runs through every formula below, from permutations to combinations with repetition.

Permutations: ordering every element

A simple permutation is an ordering that uses every one of the n available objects, as the Statistica e analisi dei dati con Python course notes from the University of Milan explain. Their number is n!, the factorial of n: multiply together every whole number from 1 to n, because the first position has n possible choices, the next has one fewer, and so on down to the last position, which is forced. The factorial is one of the few operations in algebra that outpaces any fixed power, which is why permutation counts explode even with a handful of elements.

When some of the n objects are indistinguishable from each other, say two groups of equal elements with n1 and n2 items, the Milan notes call for dividing n! by the product of the factorials of each group’s size; skip that step and orderings that only differ by swapping identical elements get counted more than once.

Arrangements: order matters, but not every element is used

Arrangements pick only k elements out of the n available, keeping order as what sets outcomes apart. In the version without repetition, an element already chosen cannot come back for the next pick: the Milan notes work out the total as n!/(n-k)!, since it amounts to a permutation stopped after k steps instead of running all the way to n.

Esempio pratico: counting 7-digit phone numbers with all digits different, drawn from the 10 digits between 0 and 9, uses exactly this formula; the Milan notes put the result at 604,800 possible numbers.

In arrangements with repetition, by contrast, the same element can turn up more than once within the same ordered group, as the Treccani Enciclopedia della Matematica also notes. The count then applies the multiplication principle k times in a row, which is n multiplied by itself k times, n raised to k. Math Is Fun walks through this with a combination lock that uses 3 digits drawn from 10 available ones: since any digit can repeat, the possible codes come to one thousand. Arrangements without repetition work the opposite way, since every pick after the first starts from one option fewer than the pick before it: ordering 3 snooker balls out of 16 available ones lands at 3,360 possibilities, far more than the matching combinations, because here every different order of the same three balls counts as its own case. The distinction between ordinal and cardinal numbers is a useful anchor: arrangements answer a question that depends on position, first, second, third, while combinations care only about quantity.

Combinations: order no longer matters

Treccani uses a hand of five cards to show the contrast: in a combination, what matters is which cards end up in your hand, not the sequence in which they were drawn, unlike an arrangement. When an element cannot come back a second time, the count is found by dividing the matching arrangements, the number of possible orderings of k elements, by k!; the result is the binomial coefficient “n choose k.”

A property of this coefficient, pointed out by Math Is Fun, is its symmetry: picking 3 balls out of 16 gives the same count of possible combinations, 560, as picking the remaining 13 out of 16.

Combinations with repetition add the option of picking an element more than once: they’re counted as the binomial coefficient n+k-1 choose k. Math Is Fun applies this by choosing 3 scoops of ice cream from 5 flavors, allowing a flavor to repeat, and the count comes to 35. The Milan notes reach the same kind of formula by rolling 3 indistinguishable six-sided dice where a value can repeat, finding 56 outcomes. Asking instead for the three faces to come up all different changes the question entirely: 120 outcomes if the dice are distinguishable and counted as an arrangement, 20 if they’re indistinguishable and counted as a combination. Which formula applies depends on whether repetition is allowed and whether the dice can be told apart.

The formulas at a glance

Type	Does order matter?	Can an element repeat?	Formula
Simple permutations	Yes, all n elements are used	No	n!
Permutations with repeated elements	Yes	equal elements already counted within the group	n! divided by the product of the factorials of each equal group
Arrangements without repetition	Yes	No	n!/(n-k)!
Arrangements with repetition	Yes	Yes	n raised to k
Combinations without repetition	No	No	binomial coefficient n choose k
Combinations with repetition	No	Yes	binomial coefficient n+k-1 choose k

A story from the 1600s to the 1700s

Per the “Analisi combinatoria” entry of the Treccani Enciclopedia Italiana, the first systematic studies on the subject appear in Blaise Pascal’s Traité du triangle arithmétique, from 1654. Gottfried Wilhelm Leibniz devotes his Dissertatio de arte combinatoria to it in 1666, John Wallis covers it in his Treatise of Algebra in 1685, and Bernard Frénicle de Bessy writes the Abrégé des combinaisons in 1693. Jakob Bernoulli returns to it in the Ars coniectandi of 1713, and Abraham de Moivre in The Doctrine of Chances of 1718: six works inside less than seventy years, spanning the late 1600s and the early 1700s.

Combinatorics comes back every time an experiment’s possible outcomes need counting, and it’s one of the building blocks behind probability and statistics: knowing how many favorable cases there are against how many total cases is the first step toward working out a probability, including the conditional kind behind the Bayes theorem. Anyone who works with number sets runs into the factorial and the binomial coefficient through these very formulas, well before seeing them applied to probability.