Do you know how to count? Really count? Conventionally, the vast majority of people would agree that they do. However, combinatorics, a domain in mathematics that involves determining the number of combinations or permutations of a given set of objects (e.g., the number of ways one can draw two aces and one king from a regular deck of cards), will challenge any preconceived ideas about "counting" that you might have.
Article Outline
An introduction to counting and the choose function
Distinguishability and Stars-and-Bars
Mathematical Identities in Pascal's Triangle
The Principle of Inclusion-Exclusion
Supplementary materials
Section 1
It's time to view counting in a new light. Let's say we have 3 apples, 4 oranges, and 4 pears, as shown below. Our goal is to find the number of unique arrangements of these fruits.
First, let's start with an easier variation on this problem: assume that each fruit, even those of the same type, are distinguishable. Therefore, all we have to account for is the number of ways we can place the fruits, regardless of order. If you imagine 11 empty positions, one for each fruit, there are 11 ways to pick which fruit will be put in the first position. Since there are 10 fruits left, there are 10 ways to pick which fruit goes in the second position, 9 ways, to pick which fruit goes in the third position,..., and 1 way to pick which fruit goes in the tenth position. Since the number of way to pick which fruit goes into which position are dependent events (i.e., if you put a fruit position x, you cannot put it in position y), we must multiply the number of ways to put fruits in each slot together, to get: 10*9*8*7*6*5*4*3*2*1=10!, where the ! symbol represents a factorial. This is a permutation.
Assuming k objects and n positions, where n >= k, the general form of a permutation is:
However, this process is a bit different if we want fruits of the same type to be indistinguishable, because the method above would actually overcount fruits of the same type. To get rid of the overcount, imagine each of the apples, for example, have a label that is either 1, 2, or 3. Since these apples are still indistinguishable, it doesn't matter if apple 1 is before apple 2, etc. Thus, we must divide our initial permutation by the number of ways to rearrange the indistinguishable apples, or 3*2*1 = 3! ways. Performing the same operation on the pears and oranges, the total number of ways to arrange these fruits is 11!/(3!4!4!) = 11,550 ways.
Analogously, we can represent this expression more cleanly (and also extrapolate to more complicated problems), using the choose function, which can be written as,
This can be read as n choose k, or picking the number of ways to arrange k objects in n spots. This is the same as what we did above, where we divided the n!/(n-k)! permutations by the number of ways to rearrange the indistinguishable objects.
Applying the choose function to the problem above,
Let's do a couple more problems to get the hang of this new operation.
Problem 1:
A set of 25 square blocks are arranged in a 5 by 5 square. How many different combinations of 3 blocks can be selected from the set such that no two are in the same row of column?
Answer:
First, let's let each block to be a location in the coordinate plane, from (0,0) to (4,4).
Each square can be thought of as a unique intersection of an x and y-coordinate. In this case, we need to pick 3 unique x and y-coordinates, and keeping in mind that these blocks are distinguishable, account for the 3! different ways to assign an x-coordinate to a y-coordinate, or vice versa, depending on how you would like to think about it. In conclusion, there are 5 choose 3 ways to pick a x-coordinate, 5 choose 3 ways to pick a y-coordinate, and 3! ways to assign a row to a column, for a total of,
unique combinations.
Problem 2: Out of a 52 card poker hand, where there are 4 cards of each of the 13 suits, are there more ways to draw 3 cards of one suit and 2 random cards or 2 cards of one suit, 2 cards of another suit, and 1 random card?
Answer:
In the first case, we must pick 1 out of 13 suits to be our card of choice, pick 3 out of 4 of the cards in that suit to be ours, and then pick two random cards. In the latter case, we need to pick 1 out of 13 cards to be our first suit, pick 2 out of 4 of the cards in that suit to be ours, repeat this process after picking another 1 out of 12 cards to be our first suit (remember, order doesn't matter), and finally pick 1 random card. This can be represented as,
Therefore, there are more ways to pick the latter.
Section 2
Determining whether the objects you are counting and the places you put them to arrange them are distinguishable or not is an important concept in combinatorics. For example, let's imagine that we have 3 balls and 4 boxes. The number of combinations of balls in boxes varies greatly depending on whether the balls and boxes are distinguishable or not.
Case 1: Both the balls and the boxes are distinguishable
There are 4 ways to place each ball in a box, or 4*4*4 = 4^3 = 64 ways in total.
Case 2: Only the balls are distinguishable
Since the boxes are indistinguishable, the only way to find distinct combinations is by whether the different balls are together or apart. Either all the balls are in the same box (1 way), two are in the same box (3 choose 2, or 3 ways), or none are together (1 way), for a total of 5 ways.
Case 3: Only the boxes are distinguishable
Only the number of balls in each box matters in this case. We thus must count the number of ways all of the boxes don't hold the same number of balls. There are 4 choose 1 = 4 ways to give one box all of the balls, 4 choose 2 * 2 =12 ways to give one box 2 balls and another 1 ball, and 4 choose 3 ways to give three boxes a ball each, giving a total of,
Case 4: Neither the balls nor the boxes are distinguishable
Only how the balls are separated matters here, or 3-0-0-0, 2-1-0-0, 1-1-1-0, without regard to ordering, for a total of 3 ways.
Now that we have a grasp on distinguishability, let's introduce a commonly used theorem in combinatorics, known as Stars-and-Bars, which is a way to enumerate the number of ways to sort k indistinguishable objects into n distinguishable bins.
First, let's note that the number of ways to have n objects and choose k of them is equivalent to the number of ways to not choose n-k objects. In other words,
Stars-and-Bars states that the number of ways to put k indistinguishable objects into n distinguishable bins is,
Applying this theorem to case 3 of our problem above, where n=4 and k=3,
We get the same result! Note that this theorem is true because finding the number of ways to put k "stars" in n boxes is the same as arranging k bars between n-1 "bars", or the spaces between the boxes. We now have n+k-1 total positions, and we need to find the number of distinct ways to choose k positions in which to place the balls.
Section 3
Odds are, you have probably seen Pascal's Triangle before, a triangle in which each non-side number is a sum of the two numbers directly above it.
However, this triangle has more mathematical splendor nestled inside of it than what may initially meet the eye... In this section, we will be exploring four combinatorial identities (one of which I discovered myself) that can be directly derived from the positioning of the numbers on Pascal's Triangle.
The Binomial Identity:
Take a look at the triangle below. The sum of the numbers in each row is a power of 2, namely for row n, the sum is 2^n. Can you extend this pattern to subsequent rows?
This pattern is due to sum of the number of possible subsets of a set, which, given a set of n items, a subset can be chosen by whether or not we include each item in the set. There are 2 ways to deal with an item, include it or exclude it. Since the choosing of each item are independent events, we must multiply the number of ways we can choose each item to get the total number of distinct subsets, or 2*2*2*2...*2 (n times) = 2^n. This is also equivalent to finding the number of ways to choose 0-n items. For example, if we have three items, we can either choose 0, 1, 2, or 3 items to be in our subset, and there is 3 choose 0, or 1 way to choose 0 items, 3 choose 1, or 3 ways to choose 1 item, 3 choose 2, or 3 ways to choose 2 items, and 3 choose 3, or 1 way to choose all the items. This theorem can be generalized as,
(note that what we would consider to be the 1st row is actually the 0th row, and the 1st entry in each row is the 0th entry)
Pascal's Identity:
Hopefully we can now view Pascal's Triangle in a different light, each number in the nth row and the kth entry of that row as the number of ways to choose k objects from n objects, instead of merely another number. If so, it is time to introduce another combinatorial identity. By definition of this triangle, any given number, as long is it is not on the edge, is a sum of the two numbers directly above it, or the kth entry in the nth row is a sum of the k-1th and kth entries in the n-1th row. We can therefore say,
For example, 4 (4th row, 1st entry) and 6 (4th row, 2nd entry) sum to 10 (5th row, 2nd entry). There are also multiple ways to interpret this result! First, through Pascal's Triangle as we did above, or through object assignments.
The number of ways to choose k objects out of n objects = number of ways to include object k1 in the selection (n-1 choose k-1, since k1 is already chosen) + number of ways to exclude object k1 in the selection (n-1 objects choose k; since we're not going to choose k we remove it from the number of possible objects to be chosen from).
A generalization of Pascal's Identity:
The true beauty of mathematics arises when you have an unexpected epiphany during the problem solving "process" (the more unstructured, the more creativity it allows!). Here I will provide you with my approximate process of discovering a generalization of Pascal's identity, so you can get insight into thinking creatively. It is important to note that I did not set out to find this generalization, but I arrived at it through some iterative experimentation with certain combinatorial ideas.
First, I was going about solving a seemingly unrelated problem: finding the number of ways to separate 10 people into a group of 4 and a group of 6 if person Alpha and person Beta in this set must be apart.
Method 1: Casework counting
If Alpha is in the smaller group (of 4), 3 more people excluding Beta must be chosen to be in that group, and the rest will automatically be in the group of 8, making 8 choose 3 possibilities. If Beta is in the smaller group, 3 people must again be chosen from the 8 remaining, which can be done in 8 choose 3 ways.
Method 2: Complementary counting
Cases in which Alpha and Beta are apart = total number of cases - cases in which Alpha and Beta are together. Thus, there are 10 choose 4 total ways to separate the people (4 in the small group, the rest in the large one, or vice versa). If they are both in the large group, there are 8 choose 4 ways to pick the other members of that group, and there are 8 choose 2 ways to pick the other members of the small group.
Equating these two methods,
Rearranging,
This equation is actually a specific case of a general identity (shown below); expand it and see for yourself!
This looks very similar to Pascal's identity, except instead of choosing whether 1 object is included, we are choosing whether 2 objects are included. The first choose function assumes Alpha and Beta are included, the second assumes either Alpha or Beta is included (multiplying by 2 to show there are 2 ways to pick which one is included), and the third chooses r+2 objects from n, instead of n+2, which explicitly excludes Alpha and Beta.
Using our complementary vs casework counting methods when we have 3 objects to choose whether to include into 2 groups, letting the c subscript be a shorthand choosing the respective objects A, B, and/or C, we get,
Extrapolating to A+B+C+... = a objects that may or may not be included,
This can also be written as,
If you want, you can use mathematical induction (base case, inductive step), which you can learn about here: https://artofproblemsolving.com/wiki/index.php/Induction, to prove this general result. Additionally, it is important to realize that the reason I included this generalization in this article was not for the end result, but the process I took to reach it, because it can be applied to practically any type of problem. So, the next time you start to see patterns in your mathematical reasoning, try to extend them as I did; it will give you a richer understanding of math, which will in turn strengthen your general intuition.
The Hockey Stick Identity:
Here's a puzzle for you: below is a pattern of numbers in Pascal's Triangle, from which you should attempt to intuitively derive The Hockey Stick Identity, or at least find a specific case. Hint: the numbers highlighted in blue can be represented as a combination of n choose the initial row, r, given the counter for rows starts at 0, and r doesn't change. How are these numbers related to the number highlighted in orange?
At the very least, you can probably see why this identity has a prefix of "Hockey Stick". Below is the identity, which is also quickly proved by induction.
Given an explicit example of this identity and the assumption that it is true for a general case for n=k, if you can show that the identity also holds for n=k+1, then it must be true for all positive integers, as k is arbitrary.
Base case:
Inductive step: assume that,
Therefore, for n=k+1,
Applying Pascal's Identity,
Section 4
This last section of this article will address a very fascinating facet of counting, namely, set theory, with the Principle of Inclusion-Exclusion, or PIE. This section will be a bit more advanced than the rest of the content in this article, so please Google parts that you don't understand and/or ask questions in the forums or in the comment section under this post.
The upside down U represents the intersection of two sets, a U represents the union of the sets, the - is the exclusion of a set, and |A| is the cardinality, or the number of elements in that set . From this diagram, we can deduce that, without loss of generality,
and,
If we were to try to find the union of all three sets, we cannot just add the elements of all of the sets together because there would be some overlap. Instead, we can perform a few compound operations, as so,
Once again, a pattern starts to emerge! Perhaps we can extend this pattern to s sets? If so, the union of all s sets would be the sum of each set, minus the sum of the intersection of the sets taken two at a time, ... , up until plus (if s is even) or minus (if s is odd) the intersection of all s sets.
Let n(s) for each 1<= s <= r be the sum of the sizes of all possible intersection of s sets chosen without repetition from A1, A2, ... , Ar. There are
ways to choose s sets, so each n(s) the sum of r choose s terms.
If we let m to be the union of the sets A1, A2, ... , Ar, and 'a' belong to k of the sets A. 'a' is counted k choose 0 times in m, k choose 1 times in n(1), k choose 2 times in n(2), ... , and k choose k times in n(k). The number of times 'a' is counted in
is
The second expression is equal to 0 due to the symmetry of the choose functions involved. Rewriting the first expression by isolating the m (union of all sets) term from the n(k) terms and then replacing the n(k)'s with our set notation,
Section 5
Supplementary materials are listed below
Combinatorics Through Guided Discovery Text: https://bogart.openmathbooks.org/pdf/ctgd.pdf
Post and view combinatorics questions and answers on Math Stack Exchange: https://math.stackexchange.com/questions/tagged/combinatorics
Combinatorics puzzles (ft. Rubik's cubes, 3D shapes, and sports balls): http://www.sfu.ca/~jtmulhol/math302/notes/permutation-puzzles-book.pdf
Commentaires