Combinatorics Explained: Everything You Need to Know

Key Points:

• The use of combinatoric methods have evolved from counting things to counting the possibility of things and even non-existent things.
• As it develops, combinatorics is even expanding from counting finite elements to objects in an infinite setting.
• Nearly every graphical function of personal computers makes use of combinatorial methods.

Combinatorics is a subset of mathematics which is devoted to the study of counting sets of elements in a finite discrete structure. There are three principles to combinatorics — addition, multiplication, and inclusion/exclusion. However, there are two formulas used to calculate combinatorics; the permutation formula and the combination formula.

Combinatorics are used for computer science applications like cryptography, data analysis, probability calculation, and programming. They allow the mathematician to analyze information around patterns, possibilities, positions, order of operations, and restrictions. Combinatorics also have many uses in the real world and can be found in a wide variety of different subjects — including military strategies, engineering, biomedicine, and transportation scheduling. However, the use for the different combinatorial methods varies depending on what the researcher/observer is trying to find.

Combinatorics: A Complete Explanation

Combinatorics is the study of counting permutations and combinations of the sets of elements within a finite structure. The entire scope of combinatorics has not been universally agreed upon, however, the most common form referred to is enumerative combinatorics which concentrates on counting the number of certain combinatorial objects. However, there is a growing subset of combinatorics subfields and approaches.

Here are the current known subsets of combinatorics mathematics:

• Enumerative combinatorics – The classic form of combinatorics, famously used for the Fibonacci sequence.
• Analytic combinatorics – Enumerative combinatorics using tools from complex analysis and probability theory.
• Partition theory – A part of number theory and analysis that is now considered an independent field in combinatorics.
• Graph Theory – Graphs are fundamental in combinatorics. The application of possibility and range is often represented visually on graphs.
• Design Theory – The study of combinatorial designs that are parts of subsets with intersecting properties.
• Finite Geometry – The study of geometric systems with a finite structure.
• Order Theory – The study of partially ordered sets whether finite or infinite.
• Matroid Theory – The study of the properties of sets of vectors in a vector space that is independent of coefficients in a linear dependence.
• Extremal combinatorics – The study of extremal questions on set systems.
• Probabilistic combinatorics – The study of the probability that certain property occurs for a random discrete object.
• Algebraic combinatorics – The use of group theory and representation theory, or other methods of abstract algebra, that apply combinatorial techniques to algebra problems.
• Geometric combinatorics – The application of combinatorics to convex and discrete geometry.
• Topological combinatorics – Combinatorial formulas are often used to help in topographical problems or in studying topology.
• Arithmetic combinatorics – Combinatorial methods that utilize only addition and subtraction.
• Infinitary combinatorics – Combinatorial set theory, or infinitary combinatorics, is the extension of combinatorics methods to infinite sets.
• Combinatorics on words – The use of combinatorics to analyze patterns within formal language.

Combinatorial problems are found in studies all around mathematics. Combinatorial solutions often cross multiple studies to create pattern analysis and solutions. The study has existed for a long time without specific reference as a subset in use for graphs even before the invention of the calculator. As graph theory and computer simulation evolved over time, the importance of higher detailed sets of data, algebra, graph information, databases, and much more pushed the study of combinatorial solutions to modern problems.

The combinatorial theory is often described as the study of counting things. While this may seem like something pure mathematics had handled, the creative design and use of combinatorics methods have gone from counting things to counting the possibility of things and even non-existent things. It is even beginning to break Its own definition by expanding from the counting of sets of elements within a finite structure to also include counting sets of elements or objects in an infinite setting.

Combinatorics: An Exact Definition

Combinatorics is a branch of mathematics that is primarily concerned with counting objects within a finite discrete structure. Mathematicians use the term to refer to a large subset of Discrete Mathematics. It contains the study of permutations and combinations. It is most often used in computer science to create formulas and analyze algorithms. While this is not all encompassing as the definition of what is considering combinatorics is expanding.

There are only three principles to combinatorics:

• Addition
• Multiplication
• Inclusion-exclusion

Some may consider permutation/combination to be the fourth principle, but these are functions of multiplication. The three principles are used to count and check for exceptions. Permutation refers to when the order of counting or operation has an impact on the result. The combination is when the order of counting or operation does not impact the result.

Combinatorics was first thought to figure out questions like “how many ways can a process be done?”. Here’s a simple example of this:

Scenario: Arrange the letters of the word TONAL so that

• T is always by L
• T and L are always together

Solve:
First, we are going to act like the letters ‘LT’ are one. This defines that we have four letters. Now, we use the combination formula to solve ( C(n, k) = n! (k! (n – k)!)). N stands for the total number of letters, or the size of the whole object list, while k represents the iteration. Solve C(4 , 4) = 4!(4!(4 -4)!). The result is C(4, 4) = 24. However, the letters L and T can be switched into two positions, or 2! Ways, either ‘LT’ or ‘TL’. Therefore, the final total of arrangements is 4!2! = 48.

In this example of enumerative combinatorics, we have taken a whole sequence and discovered the number of arrangements that can be while sticking to simple requirements.

How Do Combinatorics Work?

Combinatorics is an entire subset of mathematics devoted to counting sets of elements within a finite discrete structure. One of the commonly used examples of combinatorics is to count the total possible ways to complete a problem. As a growing branch of study, it is constantly being split into further subsets. There are two formulas used to calculate combinatorics; the permutation formula and the combination formula.

A permutation is an act of arranging all the members of a set into an order or rearranging an ordered set. It is often used when the formula is representative of a working operation where the order in which actions occur matter. For example, banks receive and lend money. They must receive the money they need in order to lend more money. This means they have to arrange transactions so that a lending request isn’t denied because the bank is out of money to lend.

The formula for the permutation of ‘x’ objects for ‘a’ selection of objects is: P(x,a) = a!/(a-x)!

A combination formula is used when the order of the members in a set makes no difference. This is used more for analytical purposes. The formula for the combination of ‘x’ objects for ‘n’ selection of objects is: C(x, n) = n!/x!.(n-x)!

Most combinatorics is used in computer science. With computer science encompassing such a large field of influence, this means it is used nearly everywhere. A more recreational purpose for combinatorics is in calculating the probability a particular event will occur. The formula for calculating the probability (P) that event ‘C’ will happen is: P(C) = Total outcomes where C occurs / Total possible outcomes.

How Do You Create Combinatorics?

The idea behind combinatorics is to choose specific objects out of a set and/or the number of ways they can be arranged. When working with combinatorics there are only a few basic rules to remember. Suppose there are two sets, A and B. Here are the rules to remember:

The Rule of Product:

The rule of product states that if there are X amount of ways to pick one element from A and Y amount of ways to pick an element from B, then X multiplied by Y will be the number of ways to pick out two elements, one from A and one from B.

The Rule of Sum:

The rule of sum states that if there are X amount of ways to pick an element from A and Y amount of ways to pick an element from B, then X plus Y will be the number of ways to pick one element that can belong to either group A or B.

Permutations with repetition:

If N objects out N1 objects are type 1, N2 objects are of type 2, … Nk objects are of type k, then the number of ways to arrange these N objects are given by: N!/(N1!N2!…Nk!)

Combinations with reptition:

If there are N elements which we want to pick K elements out of and we are allowed to choose one element multiple times, then the number of ways to pick an element out is given by:

C(N+K-1,K) = (N + K – 1)! / (K)!(N – 1)!

Using these rules, you can try out the combination calculator method on paper.

Who Created Combinatorics?

Basic concepts around combination and enumerative results have been found in ancient history. Many have been attributed with the creation of pieces of what now makes up combinatorics, but MIT states Gian-Carlo Rota as the founding father of modern enumerative combinatorics. They accredit him with transforming the methods from a bag of tricks into a deep subject. Also of note, Paul Erdos is often accredited with developing much of modern combinatorics with his studies into number theory and graph theory.

The most modern purveyor of enumerative combinatorics is Richard P. Stanley. Stanley published a two-volume book that is used as the standard introduction to enumerative combinatorics mathematics in an academic setting. Before Stanley’s publication, combinatorics was not considered to be Its own field of study and was inter-related with many other subsets of mathematics. It is for that reason that it is difficult to pinpoint the birth of combinatorics as a whole as thousands of mathematicians have contributed and expanded on what it is.

What Are the Applications of Combinatorics?

Combinatorics is a vastly growing field of mathematics. As computer technology gathers more data of unique types, there’s a need to analyze, organize, enumerate, and much more. Here’s a list of subjects combinatorics is already applied to:

• Communication networks
• Cryptography
• Network Security
• Computational Molecular Biology
• Computer Architecture
• Scientific Discovery
• Language
• Pattern Analysis
• Simulation
• Databases
• Data mining
• Homeland Security
• Operations Research
• Geometric Equations
• 3D Computational Design
• Graph Theory and Application

In theory, any subject that accrues data and requires data tracking, organization, and application may find combinatorial methods useful for their analysis and solutions. Nearly every graphical function of personal computers makes use of combinatorial methods as well. A simple example that is used by modern video games is collision detection. In collision detection, two sets of elements are compared against each other for intersections. The goal is to detect if the objects have collided or if they have not. The restriction will be that any repeated vector graph position is considered a collision. This means that all the points calculated that do not equal a collision are disregarded, while the values that equal a collision are used to determine what the object does from there based on the game’s programming.

The use case for different combinatorial methods varies depending on what the researcher/observer is trying to find. This means that there are infinite applications for the methods to mathematical problems and real-world problems that affect everyday life. It may be as mundane as improving the security of your smartphone’s banking app or communications.

Examples of Combinatorics in the Real World

Combinatorics is found in nearly every subject, which is to be expected from such a massive subset of mathematics. Here are a few examples to help make it clearer where these methods are helpful:

Military Strategy:

Resource and personnel management in dangerous situations is critical to mission success and human survival. While the military prefers to get solid Intel from trusted sources, strategists still need to calculate positions and possibilities. Using the information they can gather such as unit size, topology, resource availability, equipment, and transportation, strategists can find every possible arrangement and narrow down the best options.

Graphic Representation:

Computer graphics are based on literal graphs. The computer keeps track of positioning and draws images according to a massive graph detailing positions and changes. Even in 3D representations, graphs are utilized to represent the image shown. Combinatorics formulas are used by 3D modeling software and the computer’s operating system.

Engineering:

Pattern and image analysis are used to help graph out material studies such as heat, wind, rain, etc. This information can then be used to help shape parts that work best with exposure to specific elements. It also helps in prototyping to run a quick analysis of restriction requirements.

Biomedicine:

Molecular biology takes years of study before any tests can be put into action. This requires that analysis and theoretical possibilities are considered and mapped out in the fullest potential way.

Transportation Scheduling:

A simple, yet important, application of combinatorics is the organization of train, bus, and airplane schedules. Organizing flights or rides to passenger demand while maintaining the most efficient pathways is difficult, but permutation calculation helps to sort it out.

Organization and Design:

Whether you are planning an event or planning a coding project, combinatorial theory can help to form the best available design within your set restrictions.

Up Next…

Let’s check out these other reads on different math types.

• Here’s The Complete Guide to Boolean Logic. How do 1s and 0s end up providing the backbone to computer logic?
• The Church-Turing Thesis Explained: What it is, and When it Was Formed. This comes up in many movies and books with robots, but do you understand what the Turing test is?
• Here’s Your Complete Guide To Invariant Theory. It’s an offshoot from abstract algebra that is important for AI and machine learning.