How many ways are there to arrange “ABC“? ABC, ACB, BAC, BCA, CBA, CAB. So 6 different ways. But could we have determined it in a way that didn’t involve us listing all the cases? The answer is yes, and welcome to the wonderful world of combinatorics.
Imagine building each pattern. For the first letter, you may choose A, B, or C. So 3 options. Say we choose A, for our next letter, we only have two choices, B or C. Let’s choose B. Then your final choice is fixed, as C. So the number of patterns possible is .
In general, the number of ways to arrange a list of unique elements is . We sometimes write this as , also known as the factorial of n.
But what if they weren’t unique? How many ways are there to rearrange ABB if we don’t distinguish between the Bs?
First, lets consider the problem if we do. How many ways can we rearrange (or permute) AB₁B₂? AB₁B₂, AB₂B₁, B₁AB₂, B₁B₂A, B₂AB₁, B₂B₁A.
Notice how each one that is distinct if we don’t differentiate between Bs has a clone (where the Bs are flopped). This is the key to solving the problem in general: figure out the number of clones and get rid of them.
It’s actually quite easy to figure out how many clones there are. For example, imagine we were trying to find the number of permutations of AAAABC. Well, given a particular permutation, say ABACAA, there are a number of ways we could move the As around… The same number in fact as the number of ways we could permute A₁A₂A₃A₄: , the factorial of 4. Now, if we had distinguished between the As, there would have been ways to arrange ABACAA. So, including the clones, we have possibilities, with copies of every unique one. Dividing by the number of duplicates then allows us to get rid of them. So in this case, we divide by , this gives us .
In general, the number of permutations of a list of length with copies of one particular element is . Similarly, the number of ways to permute a list of length with copies of one element and of another is . And so on.
Now, one particularly important scenario is a list of length with As and , that is the rest, as Bs. In fact, it is so important that there is a special way of writing the number of ways to permute that list: . By the above, .
There is a lovely interpretation of this. Pascal’s triangle is constructed by starting with a one and having the elements of each proceeding row be the sum of the ones diagonally up from it, like so:
(Diagram (and subsequent ones) based on Paul Gaborit PGF/TiKz example)
Note that the value of the element in the th position of the th row is in the above diagram. This is true in general.
Why is this? Well, notice that each values is the number of paths reaching it. And the position a path reaches is uniquely determined by the number of times it goes left and right. In particular, if it takes steps and goes right times, it ends up in the th position in the th row.
For example, one can reach by going:
- Left, Right, Right
- Right, Left, Right
- Right, Right, Left
Well, how many different paths are there going to that position? How every many different permutations you can make from RRRR…LLL… : .
is important because it comes into play every time you need to repeatedly choose between two choices. A classic examples is the expansion of a binomial — so called binomial theorem.
Consider . It is the sum of all paths choosing between and . So the number of each “category” of path is where is the number of s.
(Aside: sigma notation is a way of writing the sum of a bunch of things. is a denser way of writing .)
In sigma notation, this becomes , the well-known .
There’s a lot more to be said here, but I’m leaving it to the exercises. Each one contains some interesting insight, and I spent a lot of time coming up with them. I can’t take full credit for (B) and (C): (B) was inspired by a grade 9 class mate who spent a lot of his time making the described pyramid, while (C) was is based off a comment I read on r/math a few months back.
(A) A line segment, square, and cube, are in some ways different dimension version of the same thing. Let’s call a line a 1-cube, a square a 2-cube, a normal cube a 3-cube. Higher dimensional equivalents exist and are named in he same pattern; for example, a 4D cube or tesseract, can be called a 4-cube.
- An -cube has sides, each of which is a -cube: a square has 4 sides, a cube 6, and so on. How many -cube sides-of-sides does it have? How many ?
- Why is this the case?
- Verify this for a tesseract by looking at the picture in the linked article.
(B) Pascal’s Triangle can be generalized to a pyramid, where we consider the number of downward paths to a point. The first few slices look like:
- Draw the next few slices of the pyramid.
- Why are the outer sides of the pyramid the same as Pascal’s Triangle?
- The sum of the numbers on the th level of Pascal’s Triangle is because every step each path splits in two, doubling the total number of paths. What is the sum of the numbers on the th level of Pascal’s pyramid? Why?
- What is the formula for , the value on the nth level of the pyramid, in position i on one axis and j on another.
- Why is the coefficient for in the expansion of ?
- Make a “trinomial theorem” that describes the expansion of .
- Prove your trinomial theorem using binomial theorem. (Hint: you need to use binomial theorem twice!)
(C) Some sequences of numbers look suspiciously like the levels of Pascal’s Triangle…
- Consider the powers of 11: 1, 11, 121, 1331, 14641… Why are they so similar to the levels of Pascal’s Triangle?
- Why does the next term in the sequence, 161051, break this pattern?
- Can you come up with another number that would last longer?
- Why do the powers of not look like the pyramid from (B)?
- Can you changes the rules that generate Pascal’s Triangle so that the rows look like ?
(D) Draw Pascal’s Triangle. Circle and fill in the odd numbers. The pattern that develops is a fractal called the Sierpinski triangle. Why does it form? What would happen if you did this to the pyramid from (B)?
(E) is sometimes said out loud as “ choose “ because it is the number of different sets of objects you can take from a set of size . For example, is “three choose two” in the sense that, given a set of size (or cardinality) 3, , one can get 3 subsets of size 2, , , and .
- Why is this the case?
- Using B.3, determine the total number of subsets (they can be any size!) of a set of size there are. Can you come up with a more direct reason there should be that many?
(F) The fact that binomial coefficients are always integers has an interesting implication: always divides .
- Explain how we come to this implication.
- Can you prove this theorem?
- natural numbers (positive whole numbers) are a partition of a number if . Can you generalize this property in terms of partitions?
- What does this tell you about the distribution of prime numbers?
Comments On Exercises
You may have noticed that a lot of the questions are “why” questions. That is intentional. I think we should give more “why” questions in math, in general. A “why” question can be given to people who can’t yet construct proofs and a correct answer to a “why” question contains the heart of a proof and, with some work, should be able to be converted into a proof. But the reverse doesn’t hold: it is possible to create a formal proof that is so convoluted one can not convert it into an answer of why the fact you have proved is true.
I’ll write up solutions if there is sufficient interest.