Combinatorics

From Wikiversity
Jump to: navigation, search

"There is no problem in all mathematics that cannot be solved by direct counting."-Ernst Mach

Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics. Aspects of combinatorics include "counting" the objects satisfying certain criteria (enumerative combinatorics), deciding when the criteria can be met, and constructing and analyzing objects meeting the criteria, finding "largest", "smallest", or "optimal" objects (as in combinatorial designs, extremal combinatorics and combinatorial optimization), and finding algebraic structures these objects may have (algebraic combinatorics).

Combinatorics is as much about problem solving as theory building, though it has developed powerful theoretical methods, especially since the later twentieth century. One of the oldest and most accessible parts of combinatorics is graph theory, which also has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain estimates on the number of elements of certain sets.

The first chapter Counting Principles is based completely on Enumerative Combinatorics, and includes topics such as Permutations & Combinations, Recursive Counting, Integer Partitions, Probability Theory.It also includes concepts such as Binomial Theorem and its applications to Generating Functions as well as Combinatorial Identities. Many techniques of Enumerative Combinatorics such as 'Stars and Bars' and 'Fibonacci Sequences' are deeply studied.

The second chapter Graph & Ramsey Theory discusses problems of Design Theory, Extremal Combinatorics, Configurations and Network Theory, and their solutions through the method of graphs, or systems of vertices and edges. Ramsey theory is a branch of mathematics that studies the conditions under which order must appear. Some important aspects include Paths, Colouring Problems, Adjacency Matrices, and Optimal Covers.

The third chapter Structural Algebra is about Group Theory and other Abstract Algebra topics with a combinatorial flavor. The main focus of chapter is on Permutation and Dihedral Groups, Groups as Cyclic or Dense, Infitude of Group Elements, Invariants on Group Elements, and Binary Operations on Sets. Some well known problems of this field include finding the minimum number of steps to solve any permutation of Rubik's Cube.

Chapters[edit]