DEV Community

Cover image for Combinatorics
Anita Okoh
Anita Okoh

Posted on • Edited on

Combinatorics

Combinatorics is the combination of outcomes from a finite set.
There are two major types of combinatorics.

  • Permutation
  • Combination Factors that differentiate each combinatorics are
  • Order
  • Repetition
  • Entire set/Subset

Permutation and combination both have to do with the number of different ways to arrange or pick certain elements of a set

The major differences between the two are

  • Order: For Permutation, how the set/subset is arranged or the order is very critical while for combination, the order is irrelevant. For example, trying to decode the passcode of a locker has a lot to do with how the elements/letters would be arranged. Therefore, this is a permutation problem
  • Double Counting: For Permutation, no matter how identical two subsets are in terms of elements( not order), there are still considered distinct sets. Unlike the combination, where each combination of sets should not be identical in elements. An example is a collection of the following subsets: AB, BA, AC, CA, BC. Although there are 5 permutations, there are just 3 combinations because for combinations AB & BA are not distinct selections. This is why there would be more permutation selections than combination selections in a given set. Therefore, permutation does not take into account double counting

Permutation can be split further into two

  • The vanilla Permutation
  • Variation
  1. Vanilla Permutation in the sense that all elements in the set would be used in the selection ways problem.

  2. Variation, as the name implies, infers that we pick and arrange some elements in the given set i.e a subset(s) from a total set(n)

For example, how many ways can the sets: A, B, C, D, E be arranged? can be a vanilla permutation problem while how many ways can the sets: A, B, C, D, E be arranged in twos? is a variation problem

I would like to say that combinations can be confused with variation permutation. One major difference is if the order is relevant. ( A second difference is obviously the formulas)

It is also good to know that both permutations and combinations have different formulas based on if the elements in question should be repeated or not. (combination problems with repetitions are very hard to identify)

Let's talk about the formulas. Take note of the difference in the order and repetition constraints from the image below
Alt Text

I also created a decision tree to help as well
Alt Text

The above information is not exhaustive therefore I would update as I learn more about the topic.

Top comments (0)