Intro to Combinatorics

Until I started getting into the depths of what was behind data science and statistics, I would probably have told you that 'combinatorics' was a made up word! Turns out, it is real and has really important concepts that you might already be familiar with but haven't actually put a name too. Here we're coming into the foundations behind statistics and statistical methods we might already be familiar with.

What is Combinatorics?

This area of maths deals with a combination or combinations (the combin part of combinatorics!) of objects from a specific finite set.

That still sounds rather jargon-y...so to put it another (more verbose) way: combinatorics is the part of maths that allows us to work out how likely something will happen given a definitive sample space when that "something" is a combination (or multiple combinations) of elements in the sample space and not just one individual element.

There are three broad components of combinatorics: permutations, variations and combinations. Let's introduce them one by one...

Permutations

The number of different ways we can arrange a set of elements.

If we have three elements A, B and C, the number of permutations is the numbers of ways we can 'present' these elements: ABC, ACB, BAC, BCA, CAB, CBA. There are a total of six permutations for three elements. In this example, they can be worked out manually, by picking the first element and then rearranging the remaining ones in a different order each time until they run out.

But, for more complex problems a formula comes in handy....

Pn = n x (n-1) x (n-2) x .... x 1 = n!

The equation shows that to calculate the number of permutations, given a n number of elements, is n! or n factorial. Where are factorial is the product of all the real and rational numbers up to and including n. For the example above where the number of elements is 3, the number of permutations is 3! = 1 x 2 x 3 = 6, which tallys with the manual arranging of the elements presented previously.

Variations

The total number of ways we can pick and arrange some elements of a given set.

Variations are to be used when we are not arranging all the elements in the sample space, hence the "some elements" in the definition above. For example, you have 20 people who have been called for jury duty, where there are only 12 spots. You want to work out how many variations of people you can select.

Here an equation is helpful as this is more complex to do manually. In this instance, we can not pick the same person from the pool twice. Once they've been selected, they cannot be selected again.

Variance (with no repetition) = n! / (n-p)!

n = total number of elements available, p = number of positions to be filled.

In the case of the jurors, the maths would be 20! / (20-12)! which would yield 6.0339832e+13 variations!

If you have a different scenario where you could pick a juror multiple times to be in the pool, say they got multiple votes if selected more than once the equations would be slightly different:

Variance (with repetition) = n^p

We would do 12^20, there are 12 positions to be filled and there are 20 people in the pool. This gives us a total of 3.83376e+21 options! Which expectedly is even more than above.

Combinations

The number of different ways we can pick certain elements of a set.

With combinations, it is the elements themselves that matter, the the order in which they are arranged in the subgroup. We use combinations to avoid multiple counting of elements. For instance how many combinations are there if we want to select two elements from A, B and C? Well, we can have AB (which is the same as BA), AC (which is the same as CA) and BC (which is the same as CB) - a total of 3 combinations are available.

Again, with this simple examples, it's something that we can do manually, but even then we might be missing one if we're not concentrating. So again..an equation helps us out...

Number of Combinations = Number of Variations / Number of Combinations = n! / p!(n-p)!

p = number of elements, n = sample space of n elements

In the example above with ABC, we can use this equation to confirm if we have identified all the combinations: 3! / 2!(3-2)! = 3! / 2!1! = 3! / 2! = 3, which is the number identified manually. Woo!

Symmetry of Combinations

Helpful, combinations are symmetrical, which means that the likelihood of choosing a particular combination is the same as not choosing that combination. At first it might not seem that helpful, but it is because we can use the symmetry to simplify calculations that we need to make i.e. reducing the dimension of the factorials we use.

It's worth noting, that because of this symmetry, picking more elements in a sample space can lead to fewer combinations.

Combinations with Separate Sample Spaces

A combination can also be a mixture of different smaller individual events or a mixture of combinations of elements from different sample spaces. For instance, you might be drafting a prompt for an LLM, and you have narrowed down 3 options for the question you want to ask, 4 choices of data to ask it a question about and 2 ways you want to ask the LLM to format the data. How many combinations are there of the different parts of the prompt to ask the LLM in every way possible from the options?

To calculate the number of combination options we need to multiply together the numbr of options available for each individual event. In this case: 3 x 4 x 2 = 24, so there are 24 ways to ask the LLM using these different components.

This is a great method for answering questions with the general format of "how many combinations are there to make sure we have tried all the possibilities?"

Independent Events

It might be that the events you are combining are not related to each other at all, even happening simultaneously. In this case you would calculate the product of their individual probabilities. I don't know about you, but I knew this part about independent events for a while now...but I didn't know where it came from until I started studying Combinatorics!

This was a brief introduction to some of the foundations of combinatorics. It doesn't feel super complex (hopefully!) at this point, but we are laying the groundwork for more complex statistics which are based on these concepts, so it's worth getting comfortable with these terms and equations.