Combinatorics is a branch of math concerned with counting and arranging. Most word problems that begin with "how many ways" are combinatorics problems. Did you know that there are about 1080 atoms in the universe and about 10120 different games of chess? So for every atom in the universe, there are about 1040 games of chess. Welcome to the wild world of combinatorics.
The difference between combinations and permutations is that combinations are situations where order does not matter, and permutations are situations where it does. If you have a collection of things, and you don't arrange them in any particular way, this is a combination. Every bag of marbles is a combination. If there is an arrangement, you have a permutation. So the next time your child makes you a beaded bracelet, thank them for the permutation.
---
There are four categories of counting and arranging. They are:
Permutations where repetition is not allowed
Permutations where repetition is allowed
Combinations where repetition is not allowed
Combinations where repetition is allowed
Dad likes to talk about how many different ways there are to arrange people at a dinner table. That's a permutation where repetition is not allowed.
I like to talk about flavors of ice cream scoops in an ice cream cone. That's a permutation where repetition is allowed.
Sometimes, people pick lottery numbers. The lottery is a system where people choose combinations, and repetition is not allowed.
When I was growing up, Debbie baked a dozen each of 5 types of Christmas cookies. She would give me a plate and tell me that I could choose any 4. That's a combination where repetition is allowed.
---
Dad's family was: Bill, Ruth, William, Mary, Tommy, Steve, and Pete. We'll pretend they're knights and arrange them at a round table, placing them in seats numbered 1, 2, 3, 4, 5, 6, and 7. How many different ways can the Kratzkes arrange themselves?
There are 7 ways to choose the person who sits in seat 1. Because there are only 6 people left, there are now 6 ways to choose the person who sits in the seat 2. So there are 7*6 different ways to choose Kratzkes for seats 1 and 2. For each of these 42 options, there are 5 choices for seat 3, which means there are 7*6*5 ways to designate Kratzkes into the first 3 seats. Continuing this pattern, there are 7 factorial, notated 7!, and meaning 7*6*5*4*3*2*1 ways to seat this family at the round table.
By the by, mathematicians have decided that 0! = 1, which means there is 1 way to order 0 people at a round table.
But what if the round table is pretty small, and it only seats 4 people? How many ways can we seat 4 members of the family? Well, like before, there are 7 ways to fill seat 1 and 6 ways to fill seat 2. With 4 seats, we have 7*6*5*4 ways to fill them. This is the same as 7!/3!.
Permutations with no repetitions: n! / (n - r)! , where we're choosing r out of n things.
---
I love Baskin Robbins. Their logo highlights the number 31 because they have 31 flavors. Let's say we're in the mood for a cone, and we can eat 5 scoops of ice cream. Order absolutely matters; chocolates, malts, caramels, and vanillas are more enhanced with the taste and texture of a waffle cone than fruitier flavors, and it's customary to choose something special to end on. It's kind of annoying to have two brightly flavored scoops touching; nobody would argue with the sensible decision of placing chocolate between mint and strawberry.
We have the choice of 31 flavors for our first scoop. For each of those choices, we have the choice of 31 flavors our second scoop. So there are 31*31 or 312 different ways to choose our first two scoops. Continuing this line of thinking, there are 315 different ways to choose 5 scoops of ice cream.
Multiplying everything together also works when you don't have the same number of things to choose from every time. Imagine that your significant other finds you on your stroll home. His pocket doesn't quite conceal the outline of a newly purchased jewelry box, his palms are sweaty, and trying to act nonchalant, he asks you to dinner. Before you can explain that you just ate no fewer than 5 enormous scoops of triple fudge chocolate ice cream, you find yourself gazing upon a prix fixe menu. You may choose 1 of 18 wines, 1 of 4 salads, 1 of 3 appetizers, 1 of 1 palette cleansers, 1 of 5 entrées, 1 of 4 personal sides, 1 of 3 cheese plates, and 1 of 4 desserts. You want the health insurance, so you're going to say yes. To make him feel like the luckiest guy in the restaurant, you explain that each of you has the choice of 18*4*3*1*5*4*3*4 dinners, scribbling down the beginnings of a tree diagram on his napkin.
---
If combinations are like permutations, but order does NOT matter, then there ought to be fewer combinations than permutations. There's a lottery game called "6 from 49" in which a player chooses 6 numbers from 1 to 49, never repeating a number. To calculate how many different ways there are to do this, we'll first pretend that order matters, and then we'll make that number smaller by getting rid of the duplicates.
For our first number, we have 49 choices. For our second, 48. For all 6 numbers, in which order matters, we have 49*48*47*46*45*44, which can also be expressed as 49!/(49-6)!.
But because we don't care about order, we have to divide by something to knock out the iterations with the same numbers. After all, (1, 2, 3, 4, 5, 6) is the same as (2, 1, 3, 4, 5, 6) and every other ordering of those numbers. Luckily for us, we just figured out how many orderings of the numbers 1-6 there are, and it is 6!. So if we have 6! duplicates, we need to divide 49!/(49-6)! by 6!, which yields: (49*48*47*46*45*44)/(6*5*4*3*2*1). Because the answer to "how many ways" is always an integer, these fractions will always simplify elegantly.
Let's return to the Kratzkes at the Restaurant of the Round Tables. They had such a wonderful time counting permutations last week that they have returned. But tonight is different - tonight, the hostess has announced that the table for 4 is currently available, but the table for 7 is occupied for the evening due to some grisly game involving the beheading of potential suitors. Unperturbed, the Kratzkes notice that there's a batting cage next door, so they're now faced with the decision: which 4 of them will have dinner, and which 3 will go batting? Oh, how the tables have turned! What was once a permutation problem has now become a combination problem.
We remember from before that there were 7!/3! ways to fill the 4 person table, but for the next 3 minutes, we don't care about who goes in which seat. For each selection of 4, there are 4! too many options, so we must divide by 4!.
Combinations with no repetitions is n! / [r!(n - r)!] , where we're choosing r out of n things.
This situation is called "n choose r."
---
Before we get to combinations in which repetitions are allowed, let's dwell a moment on the combinations-with-no-repetitions phrase "n choose r."
It's all written out in Pascal's triangle.
The hexagonal Pascal's triangle graphics were taken from Archimedes Lab.
Powers of 2
When we're looking for the number "n choose r," we can find it by going down to row (n + 1) and finding the term (r + 1). In the latest case of the Kratzkes, (7!)/(4!3!), we can go down to the 8th row (1, 7, 21, 35, 35, 21, 7, 1) and find the 5th term (35).
The pattern that emerges when reading Pascal's Triangle from left to right is also called "the binomial coefficient."
A polynomial is an expression made of variables and coefficients using addition, subtraction, multiplication, and powers to non-negative integers. Here's an example of a polynomial: 4a3b - b2 + 1. The only reason people get so excited about polynomials is that when polynomials are added together, they yield another polynomial.
A binomial is a polynomial with two terms. For example, (a + b) is a really good one. We could make other ones, like (4c5 - 6.789), but let's stick with (a + b).
There's a trick to expanding (a + b)n. The expansion yields a string of variables attached to the coefficients present in row (n + 1) of Pascal's Triangle. For example,
(a + b)9 = a9 + 9a8b + 36a7b2 + 84a6b3 + 126a5b4 + 126a4b5 + 84a3b6 + 36a2b7 + 9ab8 + b9.
Those coefficients can be found in row 10 of Pascal's Triangle.
These numbers, read from left to right in Pascal's triangle, also represent the binomial distribution. There's a physical board that approximates the binomial distribution, and you've probably seen it. It's called a quincunx or a Galton board, and they use one under the name "Plinko" in The Price is Right. These are peg boards in which a ball has an equal chance of bouncing left or right at each junction.
Let's switch our thinking from the quincunx to the classic binomial prop - the penny. The more pennies we flip, the less likely it is that we will flip all heads or all tails, and the more likely it is that our heads and tails count will be similar. If we skip down to the 12th row of Pascal's triangle, we can see the probability of getting some number of heads and tails if we toss a penny 11 times. In 1 out of 211 times, we will flip all tails. In 11 out of 211 times, we will flip exactly 10 heads and 1 tail. In (330 + 462 + 462 + 330) out of 211 times, we will flip 4, 5, 6, or 7 heads out of 11 chances. That's a little over 77% of the time.
---
...“and what is the use of a book,” thought Alice “without pictures or conversations?”
Addition
Squares & Sums
Extremely Fancy Numbers; Triangles in 0, 1, 2, 3, & 4 Dimensions
The Fibonacci Sequence
---
Debbie's cookies were a marvel. I had a particular fondness for the peanut butter blossoms and the pink almond maraschino cherry cookies. The other ones might have been chocolate crinkles, jam thumbprints, and Russian tea cookies; let's make it so. Debbie said I'm allowed to choose any 4.
Chocolate Crinkles - C
Jam Thumbprints - J
Maraschinos Almonds - M
Peanut Butter Blossoms - P
Russian Tea Cookies - R
There is a reason this chapter is last; combinations in which repetitions are allowed are the trickiest of them all.
We can't take 54 and then divide something out, because the cases can't agree on what that number would be. For example, imagine I chose 4 chocolate crinkles (C C C C). There are no duplicates for that pattern. But what if I chose (J M P R)? There are 4! duplicates for that one!
Nor can we pretend the set is (C C C C J J J J M M M M P P P P R R R R) and choose 4. That method would generate an excess of duplicates from choosing identical cookies.
To figure this one out, we actually have to morph the problem into a different "n choose r" situation. (Now would be a good time for me to thank the website mathisfun, which has been guiding me through this post.)
Let's put Debbie's cookies on her Christmas cookie platters. Now they look like this.
Instead of tracking our cookies, we're going to write a binary code that describes our actions.
0 means we took no cookies and moved onto the next plate.
1 means we took 1 cookie and stood still, stupidly staring at the same plate.
So if I choose 4 chocolate crinkles, that looks like this (1 1 1 1 0 0 0 0). And if I chose a jam thumbprint, a maraschino almond, a peanut butter blossom, and a Russian tea cookie, that would look like this. (0 1 0 1 0 1 0 1). This may seem convoluted, but here's where it pays off: both of these strings are 8 digits long. In other words, by tracking our actions, we can now assign comparable things to each of the cookie options. The string will always be exactly r + (n - 1) long, where r is the number of cookies Debbie is letting us have, and n is the number of types of cookies she has made.
Our question has changed from a set of 5 cookies to a string of 8 numbers, but we're still choosing 4.
"8 choose 4" on Pascal's triangle is row 9 term 5, which is 70.
Or we can use our "n choose r" formula: to get 8!/(4!4!) = 70.
---
