Combinatorics is that field of mathematics primarily concerned with counting elements from one or more sets. It can help us counting the number of orders in which something can happen.

In this article, I’m going to dwell on three different types of techniques:

  • permutations
  • dispositions
  • combinations

Permutations

Those are the easiest to compute. Imagine we have n objects, different among each others. Well, a permutation is any possible arrangement of those objects.

Consider the following example. We have a box with some balls inside (each with a different color) and we want to compute the number of ways we can arrange those balls. We can do so with two different approaches: with repetition (each ball is reinserted into the box after it is picked) or without repetition.

  • With Repetition: the idea is that, after each ball extracted, we can pick it again as many times as we want. Let’s have an easy start and consider the box={g,b}, where g=’green ball’ and b=’blue ball’: well, in that case, the possible ways we can arrange those balls are ‘gg’, ‘bg’, ‘gb’, ‘bb’. We can also compute it with Python:
box_1=['g','b']
perm=[]
for p in itertools.product(listA, repeat=2):
     perm.append(p)

perm

Output:
[('g', 'g'), ('g', 'b'), ('b', 'g'), ('b', 'b')]

Let’s do the same with 3 balls instead:

box_2 = ['g','b','y']
perm=[]
for p in itertools.product(box_2, repeat=2):
     perm.append(p)

perm
Output:
[('g', 'g', 'g'),
 ('g', 'g', 'b'),
 ('g', 'g', 'y'),
 ('g', 'b', 'g'),
 ('g', 'b', 'b'),
 ('g', 'b', 'y'),
 ('g', 'y', 'g'),
 ('g', 'y', 'b'),
 ('g', 'y', 'y'),
 ('b', 'g', 'g'),
 ('b', 'g', 'b'),
 ('b', 'g', 'y'),
 ('b', 'b', 'g'),
 ('b', 'b', 'b'),
 ('b', 'b', 'y'),
 ('b', 'y', 'g'),
 ('b', 'y', 'b'),
 ('b', 'y', 'y'),
 ('y', 'g', 'g'),
 ('y', 'g', 'b'),
 ('y', 'g', 'y'),
 ('y', 'b', 'g'),
 ('y', 'b', 'b'),
 ('y', 'b', 'y'),
 ('y', 'y', 'g'),
 ('y', 'y', 'b'),
 ('y', 'y', 'y')]

Now we have 27 possible outcomes of our experiments. If we want to generalize, when we have n objects and we want to see in how many ways we can arrange them, we have:

  • Without repetition: in this case, once you picked one ball, it cannot be used anymore. So each arrangement of balls will have unique values. In that case, coming back to our box={g,b}, the two possible permutations are ‘gb’ and ‘bg’:
import itertools 
  
box_1 = ['g','b']
perm = itertools.permutations(box_1) 
  
for i in list(perm): 
    print(i)

Output:
('g', 'b')
('b', 'g')

Again, let’s consider a bigger box ={g,b,y}, where y=’yellow ball’:

box_2 = ['g','b','y']
perm = itertools.permutations(box_2) 

for i in list(perm): 
    print(i)

Output:

('g', 'b', 'y')
('g', 'y', 'b')
('b', 'g', 'y')
('b', 'y', 'g')
('y', 'g', 'b')
('y', 'b', 'g')

In that case, we have to consider, after each extraction, that the number of available elements is one less. So, if we have n elements in our set, the permutations will be:

To let you size the difference between permutations with and without repetition, let’s visualize the example above. We have a box containing 4 balls of different colors:

We want to compute the number of possible permutations of those balls, that means: in how many ways can I arrange those balls, picking one ball at the time from the box?

If after each extraction there is no replacement, we will have that, at the first stage, there are 4 ways we can set our first element (which are yellow, green, orange and blue):

Then we pick, one by one, the other balls, and at each stage the ways we can arrange the remaining balls decrease:

Hence, at the end, we have 24 possible ways to arrange those objects, since:

On the other hand, if at the second stage (and at the following ones) we reinsert the extracted ball:

Which is equal to 256.

Dispositions

Dispositions are nothing but permutations where the number of objects we want to pick is less than the total number of objects n. Let’s simply retrieve the example above and let’s say that, out of three balls, we want to arrange only the first and second positions. Let’s use the box={g,b,y} and let’s start with the case of repetition:

  • With repetition: we want to choose two balls (k=2) out of three (n=3) and compute the number of possible permutations:
box_2 = ['g','b','y']
perm=[]
for p in itertools.product(box_2, repeat=2):
     perm.append(p)

perm

Output:
[('g', 'g'),
 ('g', 'b'),
 ('g', 'y'),
 ('b', 'g'),
 ('b', 'b'),
 ('b', 'y'),
 ('y', 'g'),
 ('y', 'b'),
 ('y', 'y')]

There are 9 possible permutations in this case, rather than 27. As in the previous case, there are n possibilities for the first choice, then again there are n possibilities for the second choice, and so on, multiplying each time. But this time, those will be multiplied not for the total number of objects (n) but just for the number of objects we are interested in (k). So we have:

Questa immagine ha l'attributo alt vuoto; il nome del file è image-119.png
  • Without repetition: the same reasoning holds if there are no repetitions. Indeed:
box_2 = ['g','b','y']
perm = itertools.permutations(box_2,2) 
  
for i in list(perm): 
    print(i)

Output:
('g', 'b')
('g', 'y')
('b', 'g')
('b', 'y')
('y', 'g')
('y', 'b')

In that case we have:

Again, let’s visualize it, considering a box with 4 balls and that we want to arrange only two of them. For a disposition with repetition we have:

While for a disposition without repetition we have:

Combinations

Combinations are dispositions (or permutations, if k=n) where the order does not matter. Basically, we use combinations whenever we want to compute in how many ways, from n objects, we can extract k of them, regardless of the order with which those are picked.

Namely, if you recall the permutation without repetition we examined at the very beginning, whose outputs were ‘gb’ and ‘bg’, the equivalent combination would be only ‘gb’ (or only ‘bg’), since the order does not matter, hence they represent the same object.

Let’s see it with python, always examining separately the two cases of repetition and no repetition:

  • With repetition:
from itertools import combinations_with_replacement 

box_1=['g','b']
comb = combinations_with_replacement(box_1, 2) 
  

for i in list(comb): 
    print(i)

Output:

('g', 'g')
('g', 'b')
('b', 'b')

As you can see, the fourth permutation ‘bg’ is not present among those combinations, since it is equivalent to ‘gb’.

The same holds with 3 balls (let’s combine only two of them):

from itertools import combinations_with_replacement 

box_2=['g','b','y']
comb = combinations_with_replacement(box_2, 2) 
  

for i in list(comb): 
    print(i)

Output:

('g', 'g')
('g', 'b')
('g', 'y')
('b', 'b')
('b', 'y')
('y', 'y')
  • Without repetition:
from itertools import combinations 

comb = combinations(box_1, 2) 
   
for i in list(comb): 
    print(i) 

Output:

('g', 'b')

And with three balls:

from itertools import combinations 

comb = combinations(box_2, 2) 
   
for i in list(comb): 
    print(i) 

Output:
('g', 'b')
('g', 'y')
('b', 'y')

The number of possible combinations (without repetition) is given by:

Which is known as Binomial Coefficient and it is used in the Binomial Probability Distribution, to compute in how many ways we can have our k successes in n trials. On the other side, if we allow repetitions, the Binomial coefficient becomes:

Again, let’s visualize it with our box of balls, with repetition:

And without repetition:

Advertisements

Published by valentinaalto

I'm a 22-years-old student based in Milan, passionate about everything related to Statistics, Data Science and Machine Learning. I'm eager to learn new concepts and techniques as well as share them with whoever is interested in the topic.

Leave a comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: