Combinatorics
Combinatorics is a vital area of mathematics focused on counting, arrangement, and combination of objects. It plays a significant role in various fields, including probability, computer science, and experimental design. The core principles of combinatorics involve basic counting methods such as the Addition Principle, which helps determine the number of outcomes when two events cannot occur simultaneously, and the Multiplication Principle, which calculates combinations when outcomes are independent. For instance, the Multiplication Principle can be applied to everyday scenarios like ordering a meal, where numerous independent choices lead to a specific number of possible combinations.
Moreover, combinatorics extends to more complex problems, including ranking individuals and forming committees, where different methods are used to account for variations in order and selection. The concept of factorial is also commonly utilized in counting arrangements, showcasing the mathematical foundation of this discipline. Combinatorial techniques are not only theoretical but also practical, aiding in decision-making processes and predictions in various applications. Understanding these principles provides valuable insights into how to systematically approach problems involving counting and arrangement.
On this Page
Subject Terms
Combinatorics
Combinatorics is a branch of mathematics that determines the number of ways that something can be done. In other words, it is the mathematics of counting. Combinatorics has numerous applications to probability, computer science, and experimental design. For example, the probability of a favorable outcome can be determined by dividing the number of favorable outcomes by the total number of outcomes. The number of ways that a set of outcomes A can occur may be represented by the symbol |A|.
One of the most basic methods in combinatorics is the Addition Principle. The Addition Principle states that if A and B cannot both occur, then the number of ways A or B can occur is computed by
A generalization of the Addition Principle is the Principle of Inclusion and Exclusion. This states that the number of ways that A or B can occur is given by
where
is the number of ways both A and B can occur.
Another basic method is the Multiplication Principle. The Multiplication Principle states that if outcome of A does not affect the outcome of B, then the combination of A and B is computed by |A||B|. As an example, consider ordering a meal at a restaurant. This boils down to a series of choices (drink, appetizer, entrée, side, and dessert), none of which affects any other choice. So if there are five choices for drink, three for appetizer, ten for entrée, seven for side, and three for dessert, then the number of meals that can ordered is 5(3)(10)(7)(3) = 3150.
The Multiplication Principle allows us to count a number of things. For example, suppose that we want to give out
different trophies to
different people in such a way that each person can receive multiple trophies or go home with nothing. There are
choices for the first trophy,
choices for the second, and so on. Hence, the Multiplication Principle gives the number of distributions as
Consider the problem of lining up
people. There are
ways to place the first person in line. Regardless of who is selected, there are
ways to place the second,
for the third, and so on. Thus, the Multiplication Principle shows that the number of ways to line up the people is
. The symbol
is read "
factorial."
Using a similar technique, we can count the number of ways to select
officers of different rank from a group of
people. Again, there are
choices for the first individual,
choices for the second, and so on, with
choices for the last individual. So the number of ways to select and rank the individuals is given by
Suppose that instead we want to determine the number of ways to select a committee of
(where every member has the same rank) from a group of
people. To do this, we can simply divide
by
, the number of ways to rank the
individuals. This results in
.
As example, consider the problem of drawing a "three of a kind" in five-card poker. There are
ways to select ranks for the hand. There are 3 ways to select which of these ranks to triple. There are
ways to select suits for the triple. There are
ways to select suits for the other two cards. Thus, the Multiplication Principle yields the number of acceptable hands as
Bibliography
Benjamin, Arthur T., and Jennifer J. Quinn. Proofs That Really Count—The Art of Combinatorial Proof. Washington, DC: Mathematical Assoc. of America, 2003.
DeGroot, Morris H., and Mark J. Schervish. Probability and Statistics. 4th ed. Upper Saddle River, NJ: Pearson, 2011.
Hollos, Stefan, J. Richard Hollos. Combinatorics Problems and Solutions. Longmont, CO:Abrazol, 2013.
Martin, George E. Counting: The Art of Enumerative Combinatorics. New York, NY: Springer, 2001.
Tucker, Alan. Applied Combinatorics. Hoboken, NJ: Wiley, 2012.