Combinatorics
Combinatorics
Combinatorics is the study of combining mathematical objects to create new arrangements. The objects may represent anything from points and numbers to apples and oranges. Combinatorics, like algebra, numerical analysis, and topology, is a major branch of mathematics. Examples of combinatorial questions are whether we can make a certain arrangement of objects, how many arrangements can be made, and what the best arrangement for a set of objects is (as judged by some mathematical criterion).
Combinatorics has grown rapidly in the last several decades, making critical contributions to computer science, operations research, finite probability theory, and cryptology. Computers and computer networks operate with finite data structures and algorithms, which makes them perfect for enumeration and graph theory applications. Leading edge research in areas like neural networking rely on the contribution made by combinatorics.
Combinatorics can be grouped into two categories. One is enumeration, which is the study of counting and arranging objects; the other is graph theory, or the study of graphs.
History of combinatorics
Leonhard Euler (1701–1783) was a Swiss mathematician who spent most of his life in Russia. He was responsible for making a number of the initial contributions to combinatorics both in graph theory and enumeration. One of these contributions was a paper he published in 1736. The people of an old town in Prussia called Königsberg (now Kaliningrad in Russia) brought to Euler’s attention a stirring question about moving along bridges. Euler wrote a paper answering the question called “The Seven Bridges of Königsberg.” The town was on an island in the Pregel river and had seven bridges. A frequently asked question there at the time was “Is it possible to take a walk through town, starting and ending at the same place, and cross each bridge exactly once?” Euler generalized the problem to points and lines where the island was represented by one point and the bridges were represented by lines. By abstracting the problem, Euler was able to answer the question. It was impossible to return to the same place by only crossing each bridge exactly once. The abstract picture he drew of lines and points was a graph, and the beginnings of graph theory. The study of molecules of hydrocarbons, compounds of hydrogen and carbon atoms, also spurred the development of graph theory.
Enumeration
To enumerate is to count. In combinatorics, it is the study of counting objects in different arrangements. The objects are counted and arranged by a set of rules called equivalence relations.
One way to count a set of objects is to ask, “how many different ways can the objects be arranged?” Each change in the original arrangement is called a permutation. For example, changing the order of the songs to be played on a compact disc (CD) player would be a permutation of the regular order of the songs. If there were only two songs on the CD, there would be only two orders, playing the songs in the original order or in reverse order, song two and then song one. With three songs on the CD, there are more than just two ways to play the music. There is the original order, or songs one, two, and three (123) and in reverse order, 321. There are two orders found by flipping the first two songs or the last two songs to get 213 or 132 respectively. There are another two orders, 312 and 231, found by rotating the songs to the right or left. This gives a total of six ways to order the music on a CD with three songs. By just trying different orders, it was intuitively seen how many combinations there were. If the CD had 12 or more songs on it, then this intuitive approach would not be very effective. Trying different arrangements would take a long time, and knowing if all arrangements were found would not be easy. Combinatorics formalizes the way arrangements are found by coming up with general formulas and methods that work for generic cases.
The power of combinatorics, as with all mathematics, is this ability to abstract to a point where complex problems can be solved which could not be solved intuitively. Combinatorics abstracts a problem of this nature in a recursive way. Take the CD example, with three songs. Instead of writing out all the arrangements to find out how many there are, think of the end arrangement and ask, “for the first song in the new arrangement, how many choices are there?” The answer is any three of the songs. There are then two choices for the second song because one of the songs has already been selected. There is only one choice for the last song. So three choices for the first song times two songs for the second choice gives six possibilities for a new arrangement of songs. Continuing in this way, the number of permutations for any size set of objects can be found.
Another example of a permutation is shuffling a deck of playing cards. There are 52 cards in a deck. How many ways can the cards be shuffled? After tearing off the plastic on a brand new deck of cards,the original order of the cards is seen. All the hearts, spades, clubs, and diamonds together and, in each suit, the cards are arranged in numerical order. To find out how many ways the cards can be shuffled, start by moving the first card to any of the 52 places in the deck. Of course, leaving the card in the first place is not moving it at all, which is always an option. This gives 52 shuffles only by moving the first card. Now consider the second card. It can go in 51 places because it can not go in the location of the first card. Again, the option of not moving the card at all is included. That gives a total of 52× 51 shuffles which equals 2, 652 already. The third card can be placed in 50 places and the fourth in 49 places. Continuing this way find to the last card gives a total of 52× 51× 50.× 4× 3× 2× 1 possible shuffles which equals about 81 with sixty-six zeros behind it—a huge number of permutations. Once 51cards were placed, the last card had only one place it could go, so the last number multiplied was one. Multiplying all the whole numbers from 52 down to one together is called 52 factorial and is written52!.
Binomial coefficients
The importance of binomial coefficients comes from another question that arises. How many subsets are contained in a set of objects? A set is just a collection of objects likethe three songs on the CD. Subsets are the set itself, the empty set, or the set of nothing, and any smaller groupings of the set. So the first two songs alone would be a subset of the set of three songs. Intuitively, eight subsets could be found on a three song CD b writing out all possible subsets, including the set itself.
Unfortunately, the number of subsets also gets large quickly. The general way to find subsets is not as easily seen as finding the total number of permutations of a deck of cards. It has been found that the number of subsets of a set can be found by taking the number of elements of the set, and raising the number two to that power. So for a CD with three songs, the number of subsets is just two to the third power, 2× 2× 2, or 8.
For a deck of 52 cards, the number of subsets comes to about 45 with fourteen zeros behind it. It would take a long time to write all of those subsets down. Binomial coefficients represent the number of subsets of a given size. Binomial coefficients are written C(r;c) and represent the number of combinations of r things taken c at a time. Binomial coefficients can be calculated using factorials or with Pascal’s triangle as seen below. (Only the first six rows are shown.) Each new row in Pascal’s triangle is solved by taking the top two numbers and adding them together to get the number below.
The triangle always starts with one and has ones on the outside.
So for our three song CD, to find the number of two song subsets we want to find C(3, 2) which is the third row and second column, or three. The subsets being songs one and two, two and three, and one and three. Binomial coefficients come up in many places in algebra and combinatorics and are very important when working with polynomials. The other formula for calculating C(r;c) is r! divided by c!× (r– c)!.
Equivalence relations
Equivalence relations is a very important concept in many branches of mathematics. An equivalence relation is a way to partition sets into subsets and equate elements with each other. The only requirements of an equivalence relation are that it must abide by the reflexive, symmetric, and transitive laws.
Relating cards by suits in the deck of cards is one equivalence relation. Two cards are equivalent if they have the same suit. Card color, red or black, is another equivalencerelation. In algebra, “equals,” “greater than,” and “less than” signs are examples of equivalence relations on numbers. These relations become important when we ask questions about subsets of a set of objects.
Recurrence relations
A powerful application of enumeration to computers and algorithms is the recurrence relation. A sequence of numbers can be generated using the previous numbers in a sequence by using a recurrence relation. This recurrence relation either adds to, or multiplies one or more previous elements of the sequence to generate the next sequence number. The factorial, n!, is solved using a recurrence relation since n! equals n × (n−1)! and (n−1)! equals (n−1)× (n−2)! and so on. Eventually one factorial is reached, which is just one. Pascal’s triangle is also a recurrence relation. Computers, being based on algorithms, are designed to calculate and count numbers in this way.
Graph theory
Graphs are sets of objects which are studied based on their interconnectivity with each other. Graph theory began when people were seeking answers to questions about whether it was possible to travel from one point to another, or what the shortest distance between two points was.
A graph is composed of two sets, one of points or vertices, and the other of edges. The set of edges represents the vertices that are connected to each other. Combinatorally, graphs are just a set of objects (the vertex set) and a set of equivalence relations (the edge set) regarding the arrangement of the objects. For example, a triangle is a graph with three vertices and three edges. So the vertex setmay be (x, y, z) and the edge set (xy, yz, zx). The actual labeling of the points is not as important as fundamental concepts which differentiate graphs.
Sometimes graphs are not easy to tell apart because there are a number of ways we can draw a graph. The graph (x, y, z) with edges (xy, yz, zx) can be drawn as a circle with three points on the circumference. The lines do not have to be straight. The vertex and edge sets are the only information defining the graph. So a circle with three distinct points on the circumference, and a triangle, are the same graph. Graphs with hundreds of vertices and edges are hard to tell apart. Are they the same?
One of a number of ways to tell graphs apart is to look at their connectivity and cycles, inherent properties of graphs.
A graph is connected if every vertex can be reached by every other vertex through traveling along an edge. The triangle is connected. A square, thought of as a graph with four vertices, (x, y, z, w) but with only two edges (xy, zw), is not connected. There is no way to travel from vertex x to vertex z. A graph has a cycle if there is a path from a vertex back to itself where no edge is passed over twice. The triangle has one cycle. The square, as defined above, has no cycles. Graphs can have many cycles and still not be connected. Ten disconnected triangles can be thought of as a graph with ten cycles. The two properties, connectivity and cycles, do not always allow for the differentiation of two graphs. Two graphs can be both connected and have the same number of cycles but still be different.
Another four properties for determining if two graphs are different is explained in a very nice
KEY TERMS
Binomial coefficients— Numbers that stand for the number of subsets of equal size within a larger set.
Combinatorics— The branch of mathematics concerned with the study of combining objects (arranging) by various rules to create new arrangements of objects.
Cycles— A graph has a cycle if there is a path from a vertex back to itself where no edge is passed over twice. The triangle has one cycle. Enumeration—The methods of counting objects and arrangements.
Equivalence relations— A way to relate two objects which must abide by the reflexive, symmetric and transitive laws.
Factorial— An operation represented by the symbol!. The term n! is equal to multiplying n by all of the positive whole number integers that are less than it.
Graph— A graph is a finite set of vertices or points and a set of finite edges.
Königsberg Bridge Problem— A common question in the Königsberg town on how to travel through the cityand over all the bridges without crossing one twice.
Network— A term used in graph theory to mean a graph with directions and weights assigned to each edge.
Permutations— Changing the order of objectsin a particular arrangement.
Recurrence relation— A means of generating a sequence of numbers by using one or more previous numbers of the sequence and multiplying or adding terms in a repetitive way. Recurrence relations are especially important for computer algorithms.
Trees— Graphs which have no cycles.
introduction to the subject, Introduction to Graph Theory by Richard Trudeau.
Computer networks are excellent examples of a type of graph that demonstrates how important graphs are to the computer field. Networks are a type of graph that has directions and weights assigned to each edge. An example of a network problem is how to find the best way to send information over a national computer network. Should the information go from Washington, D.C. through Pittsburgh, a high traffic point, and then to Detroit, or should the information be sent through Philadelphia and then through Toledo to Detroit? Is it faster to go through just one city even if there is more traffic through that city?
A similar issue involving networks is whether to have a plane make a stop at a city on the way to Los Angeles from Detroit, or if the trip be non-stop. Adding factors like cost, travel time, number of passengers, etc. along with the number of ways to travel to Los Angeles leads to an interesting network theory problem.
A traditional problem for the gasoline companies has been how to best determine their truck routes for refilling their gas stations. The gasoline trucks typically drive around an area, from gas station to gas station, refilling the tanks based on some route list, a graph. Driving to the nearest neighboring gas stations is often not the best route to drive. Choosing the cheapest path from vertex to vertex is known as the greedy algorithm. Choosing the shortest route based on distance between locations is often not the most cost effective route. Some tanks need refilling sooner than others because some street corners are much busier than others. Plus, like the Königsberg Bridge problem, traveling to the next closest station may lead to a dead end, and a trucker may have to back track. The list of examples seems endless. Graph theory has applications to all professions.
Trees
Trees are yet another type of graph. Trees have all the properties of graphs except they must be connected with no cycles. A computer’s hard drive directory structure is set up as a tree, with subdirectories branching out from a single root directory. Typically trees have a vertex labeled as the root vertex from which every other vertex can be reached from a unique path along the edges. Not all vertices can be a root vertex. Trees come into importance for devisingsearching algorithms.
Resources
Books
Bender, Edward A., and S. Gill Williamson. Foundations of Combinatorics with Applications. New York: Dover Publications, 2006.
Bona, Miklos. Combinatorics of Permutations. Boca Raton, FL: Chapman & Hall/CRC, 2004.
Brualdi, Richard A. Introduction to Combinatorics. Upper Saddle River, NJ: Prentice Hall, 2004.
David Gorsich
Combinatorics
Combinatorics
Combinatorics is the study of combining objects by various rules to create new arrangements of objects. The objects can be anything from points and numbers to apples and oranges. Combinatorics, like algebra , numerical analysis and topology , is a important branch of mathematics . Examples of combinatorial questions are whether we can make a certain arrangement, how many arrangements can be made, and what the best arrangement for a set of objects is.
Combinatorics has grown rapidly in the last two decades making critical contributions to computer science, operations research, finite probability theory and cryptology. Computers and computer networks operate with finite data structures and algorithms which makes them perfect for enumeration and graph theory applications. Leading edge research in areas like neural networking rely on the contribution made by combinatorics.
Combinatorics can be grouped into two categories. Enumeration, which is the study of counting and arranging objects, and graph theory, or the study of graphs.
History of combinatorics
Leonhard Euler (1701-1783) was a Swiss mathematician who spent most of his life in Russia. He was responsible for making a number of the initial contributions to combinatorics both in graph theory and enumeration. One of these contributions was a paper he published in 1736. The people of an old town in Prussia called Königsberg (now Kaliningrad in Russia) brought to Euler's attention a stirring question about moving along bridges . Euler wrote a paper answering the question called "The Seven Bridges of Königsberg." The town was on an island in the Pregel river and had seven bridges. A frequently asked question there at the time was "Is it possible to take a walk through town, starting and ending at the same place, and cross each bridge exactly once?" Euler generalized the problem to points and lines where the island was represented by one point and the bridges were represented by lines. By abstracting the problem, Euler was able to answer the question. It was impossible to return to the same place by only crossing each bridge exactly once. The abstract picture he drew of lines and points was a graph, and the beginnings of graph theory. The study of molecules of hydrocarbons, a compound of hydrogen and carbon atoms , also spurred the development of graph theory.
Enumeration
To enumerate is to count. In combinatorics, it is the study of counting objects in different arrangements. The objects are counted and arranged by a set of rules called equivalence relations.
One way to count a set of objects is to ask, "how many different ways can the objects be arranged?" Each change in the original arrangement is called a permutation. For example, changing the order of the songs to be played on a compact disc (CD) player would be a permutation of the regular order of the songs. If there were only two songs on the CD, there would be only two orders, playing the songs in the original order or in reverse order, song two and then song one. With three songs on the CD, there are more than just two ways to play the music. There is the original order, or songs one, two, and three (123) and in reverse order, 321. There are two orders found by flipping the first two songs or the last two songs to get 213 or 132 respectively. There are another two orders, 312 and 231, found by rotating the songs to the right or left. This gives a total of six ways to order the music on a CD with three songs. By just trying different orders, it was intuitively seen how many combinations there were. If the CD had twelve or more songs on it, then this intuitive approach would not be very effective. Trying different arrangements would take a long time, and knowing if all arrangements were found would not be easy. Combinatorics formalizes the way arrangements are found by coming up with general formulas and methods that work for generic cases.
The power of combinatorics, as with all mathematics, is this ability to abstract to a point where complex problems can be solved which could not be solved intuitively. Combinatorics abstracts a problem of this nature in a recursive way. Take the CD example, with three songs. Instead of writing out all the arrangements to find out how many there are, think of the end arrangement and ask, "for the first song in the new arrangement, how many choices are there?" The answer is any three of the songs. There are then two choices for the second song because one of the songs has already been selected. There is only one choice for the last song. So three choices for the first song times two songs for the second choice gives six possibilities for a new arrangement of songs. Continuing in this way, the number of permutations for any size set of objects can be found.
Another example of a permutation is shuffling a deck of playing cards. There are 52 cards in a deck. How many ways can the cards be shuffled? After tearing off the plastic on a brand new deck of cards, the original order of the cards is seen. All the hearts, spades, clubs, and diamonds together and, in each suit, the cards are arranged in numerical order. To find out how many ways the cards can be shuffled, start by moving the first card to any of the 52 places in the deck. Of course, leaving the card in the first place is not moving it at all, which is always an option. This gives 52 shuffles only by moving the first card. Now consider the second card. It can go in 51 places because it can not go in the location of the first card. Again, the option of not moving the card at all is included. That gives a total of 52 × 51 shuffles which equals 2,652 already. The third card can be placed in 50 places and the fourth in 49 places. Continuing this way find to the last card gives a total of 52 × 51 × 50.... × 4 × 3 × 2 × 1 possible shuffles which equals about 81 with sixty-six zeros behind it. A huge number of permutations. Once 51 cards were placed, the last card had only one place it could go, so the last number multiplied was one. Multiplying all the numbers from 52 down to one together is called 52 factorial and is written 52!.
Binomial coefficients
The importance of binomial coefficients comes from another question that arises. How many subsets are contained in a set of objects? A set is just a collection of objects like the three songs on the CD. Subsets are the set itself, the empty set, or the set of nothing, and any smaller groupings of the set. So the first two songs alone would be a subset of the set of three songs. Intuitively, eight subsets could be found on a three song CD by writing out all possible subsets, including the set itself.
Unfortunately, the number of subsets also gets large quickly. The general way to find subsets is not as easily seen as finding the total number of permutations of a deck of cards. It has been found that the number of subsets of a set can be found by taking the number of elements of the set, and raising the number two to that power. So for a CD with three songs, the number of subsets is just two to the third power, 2 × 2 × 2, or 8.
For a deck of 52 cards, the number of subsets comes to about 45 with fourteen zeros behind it. It would take a long time to write all of those subsets down. Binomial coefficients represent the number of subsets of a given size. Binomial coefficients are written C(r;c) and represent "the number of combinations of r things taken c at a time." Binomial coefficients can be calculated using factorials or with Pascal's triangle as seen below (only the first six rows are shown.) Each new row in Pascal's triangle is solved by taking the top two numbers and adding them together to get the number below.
The triangle always starts with one and has ones on the outside.
So for our three song CD, to find the number of two song subsets we want to find C(3,2) which is the third row and second column, or three. The subsets being songs one and two, two and three, and one and three. Binomial coefficients come up in many places in algebra and combinatorics and are very important when working with polynomials . The other formula for calculating C(r;c) is r! divided by c! × (r-c)!.
Equivalence relations
Equivalence relations is a very important concept in many branches of mathematics. An equivalence relation is a way to partition sets into subsets and equate elements with each other. The only requirements of an equivalence relation are that it must abide by the reflexive, symmetric and transitive laws.
Relating cards by suits in the deck of cards is one equivalence relation. Two cards are equivalent if they have the same suit. Card color , red or black, is another equivalence relation. In algebra, "equals," "greater than" and "less than" signs are examples of equivalence relations on numbers. These relations become important when we ask questions about subsets of a set of objects.
Recurrence relations
A powerful application of enumeration to computers and algorithms is the recurrence relation. A sequence of numbers can be generated using the previous numbers in a sequence by using a recurrence relation. This recurrence relation either adds to, or multiplies one or more previous elements of the sequence to generate the next sequence number. The factorial, n!, is solved using a recurrence relation since n! equals n × (n-1)! and (n-1)! equals (n-1) × (n-2)! and so on. Eventually one factorial is reached, which is just one. Pascal's triangle is also a recurrence relation. Computers, being based on algorithms, are designed to calculate and count numbers in this way.
Graph theory
Graphs are sets of objects which are studied based on their interconnectivity with each other. Graph theory began when people were seeking answers to questions about whether it was possible to travel from one point to another, or what the shortest distance between two points was.
A graph is composed of two sets, one of points or vertices, and the other of edges. The set of edges represents the vertices that are connected to each other. Combinatorally, graphs are just a set of objects (the vertex set) and a set of equivalence relations (the edge set) regarding the arrangement of the objects. For example, a triangle is a graph with three vertices and three edges. So the vertex set may be (x,y,z) and the edge set (xy,yz,zx). The actual labeling of the points is not as important as fundamental concepts which differentiate graphs.
Sometimes graphs are not easy to tell apart because there are a number of ways we can draw a graph. The graph (x,y,z) with edges (xy,yz,zx) can be drawn as a circle with three points on the circumference. The lines do not have to be straight. The vertex and edge sets are the only information defining the graph. So a circle with three distinct points on the circumference, and a triangle, are the same graph. Graphs with hundreds of vertices and edges are hard to tell apart. Are they the same?
One of a number of ways to tell graphs apart is to look at their connectivity and cycles, inherent properties of graphs.
A graph is connected if every vertex can be reached to every other vertex by traveling along an edge. The triangle is connected. A square , thought of as a graph with four vertices, (x,y,z,w) but with only two edges (xy,zw) is not connected. There is no way to travel from vertex x to vertex z. A graph has a cycle if there is a path from a vertex back to itself where no edge is passed over twice. The triangle has one cycle. The square, as defined above, has no cycles. Graphs can have many cycles and still not be connected. Ten disconnected triangles can be thought of as a graph with 10 cycles. The two properties, connectivity and cycles, do not always allow for the differentiation of two graphs. Two graphs can be both connected and have the same number of cycles but still be different.
Another four properties for determining if two graphs are different is explained in a very nice introduction to the subject, Introduction to Graph Theory by Richard Trudeau.
Computer networks are excellent examples of a type of graph that demonstrates how important graphs are to the computer field. Networks are a type of graph that has directions and weights assigned to each edge. An example of a network problem is how to find the best way to send information over a national computer network. Should the information go from Washington, D.C. through Pittsburgh, a high traffic point, and then to Detroit, or should the information be sent through Philadelphia and then through Toledo to Detroit? Is it faster to go through just one city even if there is more traffic through that city?
A similar issue involving networks is whether to have a plane make a stop at a city on the way to Los Angeles from Detroit, or should the trip be non-stop. Adding factors like cost, travel time, number of passengers, etc. along with the number of ways to travel to Los Angeles leads to an interesting network theory problem.
A traditional problem for the gasoline companies has been how to best determine their truck routes for refilling their gas stations. The gasoline trucks typically drive around an area, from gas station to gas station, refilling the tanks based on some route list, a graph. Driving to the nearest neighboring gas stations is often not the best route to drive. Choosing the cheapest path from vertex to vertex is known as the greedy algorithm . Choosing the shortest route based on distance between locations is often not the most cost effective route. Some tanks need refilling sooner than others because some street corners are much busier than others. Plus, like the Königsberg Bridge problem, traveling to the next closest station may lead to a dead end and a trucker may have to back track. The list of examples seems endless. Graph theory has applications to all professions.
Trees
Trees are yet another type of graph. Trees have all the properties of graphs except they must be connected with no cycles. A computer's hard drive directory structure is set up as a tree, with subdirectories branching out from a single root directory. Typically trees have a vertex labeled as the root vertex from which every other vertex can be reached from a unique path along the edges. Not all vertices can be a root vertex. Trees come into importance for devising searching algorithms.
Resources
books
Berman, Gerald, and K.D. Fryer. Introduction to Combinatorics. Academic Press, 1972.
Bogard, Kenneth P. Introductory Combinatorics. Harcourt Brace Jovanovic Incorporated, 1990.
Bose R.C., and B. Manvel. Introduction to Combinatorial Theory. John Wiley & Sons, 1984.
Jackson, Bradley, and Dmitri Thoro. Applied Combinatorics with Problem Solving. Addison-Wesley, 1990.
Trudeau, Richard J. Introduction to Graph Theory. Dover, 1993.
David Gorsich
KEY TERMS
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .- Binomial coefficients
—Numbers that stand for the number of subsets of equal size within a larger set.
- Combinatorics
—The branch of mathematics concerned with the study of combining objects (arranging) by various rules to create new arrangements of objects.
- Cycles
—A graph has a cycle if there is a path from a vertex back to itself where no edge is passed over twice. The triangle has one cycle.
- Enumeration
—The methods of counting objects and arrangements.
- Equivalence relations
—A way to relate two objects which must abide by the reflexive, symmetric and transitive laws.
- Factorial
—An operation represented by the symbol!. The term n! is equal to multiplying n by all of the positive whole number integers that are less than it.
- Graph
—A graph is a finite set of vertices or points and a set of finite edges.
- Königsberg Bridge Problem
—A common question in the Königsberg town on how to travel through the city and over all the bridges without crossing one twice.
- Network
—A term used in graph theory to mean a graph with directions and weights assigned to each edge.
- Permutations
—Changing the order of objects in a particular arrangement.
- Recurrence relation
—A means of generating a sequence of numbers by using one or more previous numbers of the sequence and multiplying or adding terms in a repetitive way. Recurrence relations are especially important for computer algorithms.
- Trees
—Graphs which have no cycles.