I normally discard all homework questions (I get a lot). But `georgiatehc`

is a cool kid and has been a loyal tumblr follower for quite a long time. So I wrote him a long answer summarising the spiel I used to give to combinatorics students when I taught maths. GT said it worked for him, so maybe it will work for you too.

But in general, I will still ignore homework questions.

**georgiatehc asked:**

I’m taking combinatorics and it’s kicking my butt. Do you know any good online resources I could use to supplement lectures / have any advice?

I don’t know a great resource but I at one time I was pretty good at explaining it. That said, delivery by speech and delivery by writing are not the same so I can’t guarantee this will be as beautiful and awesome as my perfectly orchestrated verbal delivery used to be.

Please get a pen and paper so you can scribble along with what I’m saying. If this were delivered in person I would draw the symbols for you. It’s not going to make sense if you just read it and don’t write anything.

Assuming from the start that you understand why there are `3! = 6`

arrangements of the letters `ABC`

.

Then the first puzzle to work out is how many distinct words can be made of `ABCD = 4!`

Why? Place a `D`

four places in any arrangement of the `3!`

`ABC`

letters `[_BAC, B_AC, BA_C, BAC_]`

hence it’s `4`

times `3!`

.

And so on. `|ABCDE| = 5!`

by the same logic and on thru `|ABCDE...HIJK...WXYZ|=26!`

.

The next puzzle is how to deal with `AABC`

… if that’s resolved then you’ll get the pattern for `AAABC`

, `AABBCC`

, and `ABCDEEEE`

etc.

There are multiple ways to solve `|AABC|`

, but one in particular generalises well.

Consider `AABC`

to comprise `A`

`₁`

and `A`

`₂`

. First imagine they are different letters so you are rearranging four things. Therefore there are `4!`

rearrangements of `A₁A₂BC`

.

Now recognise that in any given arrangement—let’s say `CA₂BA₁`

—if you dropped the subscripts you could actually swap `A₂ & A₁`

without changing the word. i.e. `CA₂BA₁ = CABA = CA₁BA₂`

.

In other words you can divide `4! / 2`

to get rid of the duplication caused by the swappable `A₁ | A₂`

.

If you want to think about that in more philosophically correct terms it’s the difference between two ways of equivalence-classing. Either treat the A’s as distinct `{A₂, A₁}`

or as the same `{A}`

.

The idea with equivalence-classing, as with category theory in some ways, is that there’s not “one right way to do it’ — we can take different viewpoints and the different answers are useful for different things. (In word problems in class: sometimes order matters, sometimes it doesn’t.)

So you’ve solved `AABC`

—what about `AAABC`

or `AAAAAAAAABC`

? And what about `AAABBBBBCC`

?

First to deal with `AAABC`

. Consider it as `A₁A₂A₃BC`

so one possible arrangement would be `BA₃CA₁A₂`

. Again you could equivalence-class the `{A₁,A₂,A₃}`

into just `{A}`

but this time instead of getting rid of swaps you would be condensing `3!`

options down into `1`

.

In other words the solution to `│AAABC│`

is `5! / 3!`

. Five for the five total letters—counting them all up as distinct—and three for the `A`

’s. (If `|ABC|=3!`

then `|A₁A₂A₃|=3!`

by renaming.)

As I said there are other ways to do these problems—but thinking about it this way:

- first counting too much,
- then modulo-ing away the stuff you don’t need

works faster when you know that `│ABCDEFGHIJK│=11!`

. You get to use that memorised trick twice (at two different equivalence-class levels) rather than have to do “hard thinking’ (enumeration).

Second, how about `│AABBBCC│`

?

There are `2+3+2=7`

total letters. In any configuration, like `B₂B₁B₃A₁C₁A₂C₂`

, you could swap the two `A`

’s `(7!/2!)`

, you could swap the three `B`

’s `(7! / 2! / 3!)`

, _and_ you could swap the two `C`

’s (`7! / 2! / 3! / 2!`

).

Why is the division cumulative? Because after you’ve *already* equivalence-classed the two `A`

’s, the three `B`

’s can *still* be equivalence-classed for an *extra* modulo `%3!`

.

That is the basic story I would tell to a student (takes ∼15 minutes which is pushing the attention boundary *hard*—requires ≥near-perfect execution). It doesn’t tell you how to classify a given word problem but it explains where the underlying calculations of the permutation & combination formulas come from.

One of those things that looks extremely scary at first, but if you genuinely walk yourself through the steps I laid out above (and give yourself a *lot* of time to digest it—like more than a few weeks) it eventually becomes as natural as “Why is `2∙3=6`

?’ Well you just … look at the rocks! It’s just the `2 groups of 3`

rocks and the `3 groups of 2`

rocks!

But remember how long it took to really understand multiplication—years? At least several months.

Maybe you can console yourself with the confidence that you can now conceive of numbers that are easily big enough to break your computer. If there are 26! permutations of the English alphabet, just conceive of a longer alphabet and your computer becomes dumber than you. For example, Unicode has (had) about 120,000 symbols — so the permutations (now you know what that means) of one appearance of each symbol would take up `~120,000!`

options. That’s a 557,389-digit number, which even `bc -l`

would choke on — but you can think it and unthink it in a blink. (Once you’ve digested the first part of my explanation.)

Also—just like there are deeper reasons for multiplication being how it is, there are deeper results like the Fundamental Theorem of Combinatorial Enumeration which I don’t really understand—and linkages to generating functions, insightful identities, groupoidification, and stuff that Real Mathematicians would talk about.

But of course you can ignore the deep stuff for now. Basically—if you grok why `│AABBBBCCC│ = 9! / 2! / 4! / 3!`

, then you can “see the maths behind’ the combinatorics problems I’ve seen—not necessarily all the honours ones but all the regular class ones.

Hopefully you have the chops from there to translate word problems into maths, once you understand what the formulas mean.