# Combinatorics

## FIELDS OF STUDY

Information Technology; Algorithms; System Analysis

## ABSTRACT

Combinatorics is a branch of mathematics that is concerned with sets of objects that meet certain conditions. In computer science, combinatorics is used to study algorithms, which are sets of steps, or rules, devised to address a certain problem.

## PRINCIPAL TERMS

• analytic combinatorics: a method for creating precise quantitative predictions about large sets of objects.
• coding theory: the study of codes and their use in certain situations for various applications.
• combinatorial design: the study of the creation and properties of finite sets in certain types of designs.
• enumerative combinatorics: a branch of combinatorics that studies the number of ways that certain patterns can be formed using a set of objects.
• graph theory: the study of graphs, which are diagrams used to model relationships between objects.

Combinatorics is a branch of mathematics that studies counting methods and combinations, permutations, and arrangements of sets of objects. For instance, given a set of fifteen different objects, combinatorics studies equations that determine how many different sets of five can be created from the original set of fifteen. The study of combinatorics is crucial to the study of algorithms. Algorithms are sets of rules, steps, or processes that are linked together to address a certain problem.

The Konigsberg bridge problem is a common example of combinatorial structures used to identify and quantify possible combinations of values. Each landmass becomes a vertex or node, and each bridge becomes an arc or edge. In computer science, these graphs are used to represent networks or the flow of computation.
THE SCIENCE OF COUNTING AND COMBINATIONS

Combinatorics is often called the “science of counting.” It focuses on the properties of finite sets of objects, which do not have infinite numbers of objects and so are theoretically countable. The process of describing or counting all of the items in a specific set is called “enumeration.” Combinatorics also includes the study of combinations, a process of selecting items from a set when the order of selection does not matter. Finally, combinatorics also studies permutations. Permutations involve selecting or arranging items in a list, when the order of arrangement is important. Combinatorics also studies the relationships between objects organized into sets in various ways.

There are numerous subfields of combinatorics used to study sets of objects in different ways. Enumerative combinatorics is the most basic branch of the field. It can be described as the study of counting methods used to derive the number of objects in a given set. By contrast, analytic combinatorics is a subfield of enumerative combinatorics. It deals with predicting the properties of large sets of objects, using quantitative analysis. All combinatorics analysis requires detailed knowledge of calculus. Many sub-fields make extensive use of probability theory and predictive analysis.

COMBINATORICS APPLICATIONS

There are many different applications for combinatorics in analytic mathematics, engineering, physics, and computer science. Among the most familiar basic examples of combinatorics is the popular game sudoku. The game challenges players to fill in the blanks in a “magic square” diagram with specific column and row values. Sudoku puzzles are an example of combinatorial design, which is a branch of combinatorics that studies arrangements of objects that have symmetry or mathematical/geometric balance between the elements.

Combinatorics is also crucial to graph theory. Graph theory is a field of mathematics that deals with graphs, or representations of objects in space. Graphs are used in geometry, computer science, and other fields to model relationships between objects. In computer science, for instance, graphs are typically used to model computer networks, computational flow, and the structure of links within websites. Combinatorics is used to study the enumeration of graphs. This can be seen as counting the number of different possible graphs that can be used for a certain application or model.

COMBINATORICS IN ALGORITHM DESIGN COMBINATORICS IN CODING

Combinatorics is also used in coding theory, the study of codes and their associated properties and characteristics. Codes are used for applications, including cryptography, compressing or translating data, and correcting errors in mathematical, electrical, and information systems. Coding theory emerged from combinatorial analysis. These two branches of mathematics are distinct but share theories and techniques. Combinatorics is an advanced field of study. The arrangement, organization, and study of relationships between objects provides analytical information applicable to many academic and practical fields. Combinatorics influences many aspects of computer design and programming including the development of codes and the precise study of information and arrangement of data.

—Micah L. Issitt

Beeler, Robert A., How to Count: An Introduction to Combinatorics. New York: Springer, 2015. Print.

“Combinatorics.” Mathigon. Mathigon, 2015. Web. 10 Feb. 2016.

Faticoni, Theodore G., Combinatorics: An Introduction. New York: Wiley, 2014. Digital file.

Guichard, David. “An Introduction to Combinatorics and Graph Theory.” Whitman. Whitman Coll., 4 Jan 2016. Web. 10 Feb. 2016.

Roberts, Fred S., and Barry Tesman. Applied Combinatorics. 2nd ed. Boca Raton: Chapman, 2012. Print.

Wagner, Carl. “Choice, Chance, and Inference.” Math.UTK.edu. U of Tennessee, Knoxville, 2015. Web. 10 Feb. 2016.