The combinatorial calculus…

The combinatorial calculus studies the groupings that can be obtained with a given number n of objects arranged on a given number k of places.

The groupings can be formed without repetitions or with repetitions of the n objects.

According to Wikipedia: Factorial of a positive integer n, denoted by n! is the product of all positive integers less than or equal to n.

You can calculate factorials with the following formula:

\(n! = n \times \left( {n – 1} \right) \times \ldots \times 2 \times 1 = \prod\limits_{i = 1}^n i \)

Now you might be wondering how you would go about calculating factorials in Python. While I’m certain in the existence of out-of-the-box functions in various libraries, it’s really easy to define your own function, and that’s exactly what we’ll do.

Here’s a simple recursive function which will get the job done:

def factorial(n):
    if n == 1: return 1
    else: return n * factorial(n-1)

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word “permutation” also refers to the act or process of changing the linear order of an ordered set. In other words, they are the groupings made when the number of objects equals the number of places and counts the order in which they are arranged. Permutations can be without repetitions of objects or with repetition of objects. In particular, we will talk about permutations if the number of objects corresponds to the number of places; if the number of objects is different from the number of places, we will speak of dispositions instead.

A combination is a selection of items from a collection, such that (unlike permutations) the order of selection does not matter.

Let’s work this out with an example.

You have a website on which users can register. They need to provide a password that needs to be exactly 8 characters long, and characters cannot repeat. We first need to determine how many characters and digits there are in the English alphabet:

  • the number of letters: 26
  • the number of digits: 10

Which is 36 in total. So n = 36. r would then be 8, because the password needs to be 8 characters long. Once we know that, it’s easy to calculate the number of unique passwords, given the following formula:

\(D_{n,k}=\frac{{n!}}{{\left( {n – r} \right)!}}\)

If you went ahead and calculated by hand:

\(\frac{{36!}}{{\left( {36 – 8} \right)!}} = 1220096908800\)

Or even in Python, it really is a trivial task:

def factorial(n):
    if n == 1: return 1
    else: return n * factorial(n-1)

def disposition_without_repetition(n,r):
    return (factorial(n) / factorial(n-r))


m= disposition_without_repetition(36, 8)
print(m)

Okay, cool, but I want to allow my users to repeat characters. No problem, in that case, we’re talking about dispositions with repetition, and the formula is even simpler:

\(D_{n,k}^r = {n^k}\)

You already know what n is 36, and what r is 8, so here’s the solution:

def factorial(n):
    if n == 1: return 1
    else: return n * factorial(n-1)

def disposition_without_repetition(n,r):
    return (factorial(n) / factorial(n-r))

def disposition_with_repetition(n,r):
    return n ** r


m= disposition_with_repetition(36, 8)
print(m)

or:

\(D_{36,8}^r=36^8=2821109907456\)

That’s a whole lot of password options.

How many anagrams, even without meaning, can be formed with the word “MAMMA”?

In this case, the order counts, but the five letters are not all distinct: M is repeated 3 times; A is repeated 2 times.

\(P_n^r = \frac{{5!}}{{3! \cdot {2_2}!}} = \frac{{120}}{{6 \cdot 2}} = 10\)

or, in different words, there are 10 words that can be formed with the letters of the word MAMMA.

Now, consider the following sentence: A group of people selected for a team is the same group, the order doesn’t matter. That’s the whole idea behind combinations. If you select 5 members for the team, you could order them by name, height, or something else, but essentially you would still have the same team — ordering is irrelevant.

So, let’s formalize this idea with a formula. The number of combinations C of a set of n objects taken r at a time is calculated as follows:

\(\boldsymbol{C}(\boldsymbol{n}, \boldsymbol{r})=\frac{\boldsymbol{n} !}{\boldsymbol{r} !(\boldsymbol{n}-\boldsymbol{r}) !}\)

Now you can take that equation and solve the following task: On how many ways can you choose 5 people from a group of 10 for a football team?

The group would be the same, no matter the ordering. So let’s see, n would be equal to 10, and r would be 5:

\(C\left( {10,5} \right) = \frac{{10!}}{{5!\left( {10 – 5} \right)!}} = 252\)

This can once again be easily done with Python:

def factorial(n):
    if n == 1: return 1
    else: return n * factorial(n-1)

def disposition_without_repetition(n,r):
    return (factorial(n) / factorial(n-r))

def disposition_with_repetition(n,r):
    return n ** r

def combinations_without_repetition(n,r):
    return (factorial(n)/(factorial(r) * (factorial(n-r))))



m= combinations_without_repetition(36, 8)
print(m)

Great! But now you might be wondering if there exists a version of combinations which allows repetition. The answer is yes. I’ll explain now.

Assigned two droppers, the first contains 5 drops of white color and the second 5 drops of black color. By mixing 5 drops chosen between the two, how many different colors can be formed?

Answer:

\(C_{2,5}^r = \frac{{\left( {2 + 5 – 1} \right)!}}{{5!\left( {2 – 1} \right)!}} = \frac{{6!}}{{5! \cdot 1!}} = 6\)

def factorial(n):
    if n == 1: return 1
    else: return n * factorial(n-1)

def disposition_without_repetition(n,r):
    return (factorial(n) / factorial(n-r))

def disposition_with_repetition(n,r):
    return n ** r

def combinations_without_repetition(n,r):
    return (factorial(n)/(factorial(r) * (factorial(n-r))))

def combinations_with_repetition(n,r):
    return ((factorial(n+r-1))/(factorial(r)*(factorial(n-1))))


m= combinations_with_repetition(2, 5)
print(m)