Help! I’m struggling with basic combinatorics!

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!.

 

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 that generalises well.

Consider AABC to be composed of 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.

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.

Advertisements

Tags: , , , , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: