Permutations and Combinations

Permutations and combinations are the two basic ways of counting how many selections can be made from a set of items. A permutation is an arrangement in which order matters: first, second and third place in a race is a permutation of the runners. A combination is a selection in which order does not matter: a committee of three chosen from the same group is a combination. Together they form the core of combinatorics, the branch of mathematics concerned with counting.

Counting underlies probability, since the chance of an event is often the number of favourable outcomes divided by the number of possible ones. In finance, permutations and combinations appear in option pricing on a binomial tree, in working out how many portfolios or pairs can be formed from a universe of assets, and in judging how many strategies a researcher has implicitly tested.

The number of permutations of $r$ items chosen from $n$ distinct items is:

The number of combinations of $r$ items chosen from $n$ is:

• $n$ is the number of items available.
• $r$ is the number chosen.
• $n!$, read as n factorial, is the product of all whole numbers from 1 to $n$. By convention $0! = 1$.

The two are linked. Each combination of $r$ items can be arranged in $r!$ different orders, so $P(n, r) = C(n, r) \times r!$. There are always at least as many permutations as combinations.

A fund manager must rank a first, second and third choice from five shares. Order matters, so the count is $P(5, 3) = 5! / 2! = 5 \times 4 \times 3 = 60$. If the manager simply needs to pick three of the five to hold in equal amounts, order does not matter, and the count is $C(5, 3) = 60 / 3! = 10$.

A researcher wants to examine every possible pair among 50 shares for a pairs trading strategy. The number of pairs is $C(50, 2) = (50 \times 49) / 2 = 1{,}225$. Among 500 shares it is $C(500, 2) = 124{,}750$. The count grows roughly with the square of the number of shares, which has practical consequences discussed below.

Combinations give the number of ways a fixed number of successes can occur in a series of independent trials. If each trial succeeds with probability $p$, the probability of exactly $k$ successes in $n$ trials is:

This is the binomial probability distribution. Suppose a share is equally likely to rise or fall each day. The probability of exactly six up days in ten is $C(10, 6) \times 0.5^{10} = 210 / 1{,}024 = 0.205$, or about 20.5 percent.

The same counting drives the binomial option pricing model. The model divides the life of an option into steps, at each of which the price of the underlying moves up or down. After $n$ steps, the number of distinct paths that contain exactly $k$ up moves is $C(n, k)$, and all of them end at the same price. With four steps there are $C(4, 2) = 6$ paths with two up moves and two down moves, but only one path with four up moves. Weighting each final price by the number of paths that reach it, and by the probability of each path, gives the expected value of the option's payoff.

Combinatorial growth explains why data mining is so dangerous in trading research. The 124,750 pairs available among 500 shares, each tested for cointegration at the 5 percent level, would produce more than 6,000 apparent relationships by chance even if none were real. A strategy with five parameters, each tried at ten settings, has $10^{5} = 100{,}000$ versions. Choosing 5 indicators from a library of 40 can be done in $C(40, 5) = 658{,}008$ ways. The best of so many candidates will look impressive in a backtest whether or not it has merit, which is the essence of overfitting. Knowing the size of the search is the first step in correcting for it.

The same arithmetic applies to portfolio construction. The number of ways to choose 30 shares from an index of 500 is astronomically large, far beyond exhaustive search, which is why portfolio optimization relies on mathematical methods instead of enumeration.

Several variations cover cases the basic formulas do not. When items may be chosen more than once, the number of ordered selections is $n^{r}$. A four-digit code using ten digits has $10^{4} = 10{,}000$ possibilities. When some items are identical, the count of distinct arrangements is reduced by dividing by the factorials of the repeated groups. Factorials grow extremely fast, so for large problems the counts are estimated with approximations or explored by random sampling and Monte Carlo simulation instead of being listed in full.

In machine learning, a combinatorial form of cross-validation splits a data set into groups and tests on every possible combination of them, producing many test paths from a limited history. Counting principles also sit behind the rules of conditional probability, where the number of outcomes consistent with a given condition replaces the total number of outcomes.