Dad was being annoying again. He told me
not to write a post on permutations, combinations, Pascal's triangle, and binomial coefficients, and then he said, "Just find some time to have a conversation with Drakeson about it." But in order to have a conversation, I need to know what I'm talking about, and for that to happen, I have to write a post.
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.
Milli tries to bring too many bottles of hand sanitizers on the plane to WA for summer vacation. She's stopped by TSA and has to make some decisions. That's a combination where repetition is not allowed.
When I was growing up, Debbie baked a dozen each of 6 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. Let it be known that seat 1 is the head of the table. 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? (Seat 1 is still the head of the table.) 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. Furthermore, 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 beverage napkin.
---
If combinations are like permutations, but order does NOT matter, then there ought to be fewer combinations than permutations.
Milli has acquired 24 different types of hand sanitizers, all in 2 oz bottles. When packing for her trip to WA, she has chosen to bring them all. The transportation security officer, Madge, explains the 3-1-1 liquid rule: bottles must be 3.4 oz or smaller, they must all fit into a 1 quart sized clear plastic bag, and each passenger is allowed exactly 1 bag. Milli realizes she can fit 6 hand sanitizers into a quart sized bag and asks Madge how many ways she can choose 6 from 24.
Charmed, Madge replies, "First we need to pretend that order matters and calculate the permutation. Then we'll make that number smaller by dividing in order to get rid of the duplicates. For our first hand sanitizer, we have 24 choices. For our second, 23. So to select all 6 bottles, we have 24*23*22*21*20*19 choices, which can also be expressed as 24!/(24-6)!."
Milli nods in agreement. Madge continues. "But because we don't care about order, we have to divide by something to knock out the duplicate sets. Do you know how many ways there are to order each set of 6 hand sanitizers?" Milli replies, "Of course. Six factorial." Madge nods approvingly and continues, "So if we have 6! duplicates, we need to divide 24!/(24-6)! by 6!, which yields: (24*23*22*21*20*19)/(6*5*4*3*2*1). And because the answer to "how many ways" is always an integer, these fractions will always simplify elegantly."
Milli thanks Madge, procures 4 clear quart sized bags out of nowhere, packages up 4 bags of 6, and distributes them among her dad, mom, and brother.
Let's return our attention 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 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 brand new carnival & batting cage next door, and to attract future business, it's running a promotion where everybody with the letter "z" in their last name attends free of charge. This means they're now faced with the decision: which 4 of them will have dinner, and which 3 will go to the carnival? Oh, how the tables have turned! What was once a permutation problem has now become a combination problem.
Let's focus on one question - which 4 of them will have dinner? We remember from before that there were 7!/3! ways to fill the 4 person table, but for the next few minutes, we don't care about who goes in which seat. For each selection of 4, there are 4! duplicates, so we must divide 7!/3! by 4!.
Combinations with no repetitions: 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.
These 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 more polynomials.
A binomial is a polynomial with two terms. For example, (a + b) is a really good one. We can 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 from row (n + 1) of Pascal's Triangle. For example,
(a + b)9 = a9 + 9a8b + 36a7b2 + 84a6b3 + 126a5b4 + 126a4b5 + 84a3b6 + 36a2b7 + 9ab8 + b9.
Those coefficients are in row 10.
These strings of numbers in Pascal's triangle, read from left to right, 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 we'll flip all heads or all tails, and the more likely it is that our heads and tails counts will be closer together. If we look at 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'll flip all tails. In 11 out of 211 times, we'll flip exactly 10 heads and 1 tail. In (330 + 462 + 462 + 330) out of 211 times, we'll 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
Integers - line segments or 1D triangles
Triangular Numbers - triangular grid in 2D (like bowling pins)
Tetrahedral Numbers - pyramids in 3D where all sides are triangular numbers
Pentatope Numbers - hard to understand; triangles in 4D
The Fibonacci Sequence
---
Debbie's cookies were a marvel. I had a particular fondness for the peanut butter blossoms, and Angel loved the chocolate crinkles. Amongst the others were peppermint candy cookies, green tree almond press cookies, frosted maraschino chocolate cookies, and Aunt Katherine's caramel cups. You might recall that Debbie said I'm allowed to choose any 4.
Aunt Katherine's - A
Blossoms - B
Chocolate Crinkles - C
Drop Peppermints - D
Evergreens - E
Frosted Maraschinos - F
There's a reason this chapter is last; combinations in which repetitions are allowed are the trickiest of them all.
We can't take 64 and then divide something out, because the cases can't agree on what that number would be. For example, imagine I chose 4 Aunt Katherine's (A A A A). There are no duplicates for that pattern. But what if I chose (B C D E)? There are 4! duplicates for that one.
Nor can we pretend the set is (A A A A B B B B C C C C D D D D E E E E F F F F) and choose 4. The permutation would be 24*23*22*21, but just like before, we wouldn't know what to divide by. Again, (A A A A) would yield no duplicates and (B C D E) would yield 4!.
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 writing this entire post.)
Let's put Debbie's cookies onto her Christmas cookie platters. Now they look like this:
Instead of tracking our cookies, we're going to write a code that describes our actions.
M - we MOVE to the next plate, taking to cookies.
T - we TAKE 1 cookie and stand still, stupidly staring at the same plate.
So if I choose 4 Aunt Katherine's, that looks like this (T T T T M M M M M). And if I choose a blossom, a chocolate crinkle, a drop peppermint, and an evergreen, that looks like this (M T M T M T M T M).
This may seem convoluted, but here's where it pays off: both of these strings are 9 digits long. By tracking our actions instead of our cookies, we can represent each choice in a way that lends itself to factorials and division once again. 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.
How many ways can we distribute T's? Our question has changed topics from a set of 6 cookies to a string of 9 actions, but we're still choosing 4. And "9 choose 4" on Pascal's triangle is row 10 term 5, which is 126. Or we can use our "n choose r" formula to get 9!/(4!5!) = 126.
| choosing r out of n | repetition not allowed | repetition allowed |
| permutations, order matters | n! / (n - r)! | nr |
| combinations, order doesn't matter | n! / [r!(n - r)!] | (r + n - 1)! / [r!(n - r)!] |
