Counting

September 21, 2011 10:16 AM

Counting is one of the first and simplest concepts most people are taught. But when you get beyond simple 123s, counting can become an advanced subject all its own. Essentially the science of counting, combinatorics is a key component of everything from abstract algebra to probability (PDF).

Basic combinatorics (such as the number of ways can you choose a 3-person committee from 5 potential candidates) can be accessible to those with basic mathematical knowledge. Advanced topics such as Ramsey Theory can give rise to things like Graham's Number, so large that even stacked exponential notation cannot be used to describe it. Combinatorics was also one of Erdös's favorite subjects (PDF, combinatorics article starts on page 5).

Want to dive in yourself?

• Carl Wagner offers an introductory text (PDF) covering probability and statistics as well.
• Similarly, a George Tech course intro (PDF) on combinatorics.
• MathReference has a basic tutorial, thought the site layout and navigation are a bit cumbersome.
• OpenCourseWare has an undergrad level combinatorics course here.

(Advanced counting can also lead to infinity, covered previously.)

posted by kmz (38 comments total)

Woo-hoo! Now if I could figure out something to do with the alphabet.
posted by dances_with_sneetches at 10:22 AM on September 21, 2011 [1 favorite]

Ramsey Theory has the shortest distance between "obvious" and "my brain is melting" of any area of mathematics.
posted by benito.strauss at 10:23 AM on September 21, 2011 [3 favorites]

the number of ways can you choose a 3-person committee from 5 potential candidates) can be accessible to those with basic mathematical knowledge.

That sounds easy, but in practice you have to consider that the 3-person committee is made from 5 potential candidates, three of which belong to the same political party as the chooser, two went to school with him, one of them favors partial-birth abortions, four of them received funding from the same donors as the one choosing, four of them are the same gender, one is gay, another voted against in a recent vote...

Really, combinatorics is not for the apolitical.
posted by twoleftfeet at 10:23 AM on September 21, 2011 [1 favorite]

Now if I could figure out something to do with the alphabet.

That's where combinatorics on words comes in.
posted by kmz at 10:23 AM on September 21, 2011 [1 favorite]

Basic combinatorics (such as the number of ways can you choose a 3-person committee from 5 potential candidates)

My combinatorics professor liked to describe it as "the number of ways you can give candy bars to children." There are, in turn, a number of different ways to ask that question:

• How many ways can you give n candy bars to m children?
• What if the children are uniquely identified (e.g. they have names)?
• What if the candy bars are uniquely identified (e.g. they are each a different kind)?
• What if each child has to get at least one bar?
• What if the candy bars have different dollar values and you want to minimize the difference between each child's take?
• What if it matters in what order you give the candy bars out?
• What if the candy bars are not uniquely identified but are of different brands (e.g. you want to hand them out without giving any child two of any given kind of candy bar)?

And then you can combine each of these twists, so for example what if the children have unique names, there are several different brands of candy bar, each child has to get at least one, but you don't want to give any child more than one of the same brand?
posted by jedicus at 10:29 AM on September 21, 2011

My combinatorics professor liked to describe it as "the number of ways you can give candy bars to children."

Don't accept combinatorics from strangers, children.
posted by twoleftfeet at 10:31 AM on September 21, 2011 [2 favorites]

Now *this* is a FPP!
posted by facetious at 10:33 AM on September 21, 2011 [1 favorite]

My combinatorics professor liked to describe it as "the number of ways you can give candy bars to children."

Which reminds me of how I've heard prepositions described: Anything a fly can do to a cup (or anywhere a mouse can go).
posted by DU at 10:34 AM on September 21, 2011 [1 favorite]

I see how many you did there.
posted by penduluum at 10:39 AM on September 21, 2011 [4 favorites]

How many ways can you give n candy bars to m children?
• What if the children are uniquely identified (e.g. they have names)?
• What if the candy bars are uniquely identified (e.g. they are each a different kind)?
• What if each child has to get at least one bar?
• What if the candy bars have different dollar values and you want to minimize the difference between each child's take?
• What if it matters in what order you give the candy bars out?
• What if the candy bars are not uniquely identified but are of different brands (e.g. you want to hand them out without giving any child two of any given kind of candy bar)?

I love it when MetaFilter writes my exams for me. This is exactly where we've gotten to (occupancy problems) in class this semester, and I like this set of questions. (although treating children as indistinguishable boxes will require some careful question-phrasing.) I once wrote a quiz that was entirely candy-themed (the quiz was on Valentine's day), with occupancy problems of this type (distributing M&Ms, or valentines, or filling boxes with chocolates).

---

One of my favorite problems to talk to people about when they ask "so, you do math. Do you do really hard arithmetic all day?" is the following (combinatorial---so I'm not off-topic, promise!) question:

You have a number of committees. Various committees have various members. Some people serve on only one committee, while others serve on several. How do you determine the smallest number of meeting times needed so that no person is expected to be in two committee meetings at once?

One way to approach solving the problem is as follows: Represent each committee by a vertex (a big dot). Connect two vertices with an edge (a line segment, although we don't care if it wiggles) if the two committees have a member in common. Now you have translated the committee scheduling question into a question about a mathematical object called a graph. [Note that if you took high-school math, this graph is not the plot of all points (x, f(x)) of some function, f, but rather an entirely different kind of mathematical object also called a graph. This is the kind of object that graph theory studies.]

Ok, so now we have a graph that represents the committee scheduling problem. How do we solve the problem? Well, we want to color the vertices of the graph so that if two vertices are connected with an edge, they have different colors, and we want to use the fewest number of colors possible. For small graphs, this coloring problem is fairly easy (there are even iPhone apps that take the graph coloring problem and say, hey, look, a game! e.g. NetColoring). For large graphs, this problem is hard in a mathematical precise way, but there are algorithms to help you.

So, we translated the committee scheduling problem into a more general problem of how to color the vertices of a graph, and then this problem is well-studied by mathematicians and computer scientists. Neat!

You can also impose restrictions: if you only have two possible time slots, then you want to know whether the corresponding graph is bipartite (= 2-colorable). If you have 4 time slots, but for one of the slots, there is only one room available to meet in, then you are asking if you can color the graph with 4 colors so that one color is only used once.

And if you had a big enough computer, presumably you could use this same technique to...say...schedule final exam times to minimize the length of the final exam period (and thus save the university money!). And there are lots of other things you can model as graph coloring problems as well.
posted by leahwrenn at 10:55 AM on September 21, 2011 [10 favorites]

Anyone unfamiliar with them should check out generating functions, which let you bring calculous and differential equations to bear on counting problems, or conversely. I recommend Generatingfunctionology by Wilf.
posted by jeffburdges at 11:11 AM on September 21, 2011 [5 favorites]

A general post about the entire 05 area code is pretty vague.

But this idea of "advanced counting" is something that a broad audience should be aware of. In particular, the idea that it's still possible to count, and to work with numbers, way beyond 123... etc.

The basic formulas of combinatorics - I mean, combinations and permutations - rely on factorials. The notation is like this:
3! = 3X2X1 = 6
4! = 4X3X2X1 = 24
5! = 5X4X3X2X1 = 120
(we say "three factorial is 6, four factorial is 24, five factorial is 120, etc.)
So if we write 50! we mean 50X49X48X47X46X45X... and so on, until finally we multiply by one.

These numbers get really big, really fast. You can see from this list that these numbers are hard to write down, eventually. Google will happily tell you the value of 170 factorial, but it doesn't even try when you get to 171 factorial.

Already at 170! we have a number that is unimaginably huge. By "unimaginably", I mean that there is very little you could do to try to imagine anything that big. 170! seconds is around 10 to the 300th years (= 10^300 years). The age of the universe is around 13 billion years (= 13 X 10^9 years). If every cell in every human body that ever lived had an entire universe's worth of lifetime, the total number of seconds wouldn't be as big.

But imagining these big numbers isn't the point.

The point is that these kinds of big numbers show up all around us, all the time.

For example, in a horse race involving 3 horses (call the horses A, B, and C), there are only six ways the race can end. Either A, B, or C can win first place. (3 possibilities). For each possible winner, there are only 2 remaining horses that can finish second, and then, given first and second places, there is only one horse left to finish in third place. So there are 3X2X1 = 6 ways these three horses can end the race (here's a list: ABC, ACB, BAC, BCA, CAB, CBA). In a race with seven horses, there are 7!= 7X6X5X4X3X2X1 = 5040 ways the race can end.

Now, many decisions about information, and many ways of structuring those decisions, involve putting many things into some kind of order, like the horses in a race. So these kinds of unimaginably large numbers show up much more often than we might imagine.

It's worth learning to think about how to count possibilities that big, so big that you could never count all the possibilities in a zillion lifetimes.

That's a reason to study combinatorics.
posted by twoleftfeet at 11:34 AM on September 21, 2011 [3 favorites]

leahwrenn: a big enough computer

It's been a while since I studied the subject so please correct me if I'm wrong, but my understanding was that, to find the best solution for problems with real world complexity "Big enough" usually involves converting all available matter on the planet/solar system/galaxy/universe into a single computer, and then letting it run until the universe ends.
posted by Grimgrin at 11:39 AM on September 21, 2011

Nice post!

Combinatorics is one of those areas of math that has become foundational -- indeed, anybody doing mathematical research (or at least research in pure math) needs to know at least some basic results in the field. For example, I recently had to learn the basics of Gaussian binomial coefficients for some research I'm doing.

It's worth mentioning that for pretty much any subject area in pure math, you can add "combinatorial" in front of it and get an active area of research -- combinatorial algebraic geometry, combinatorial representation theory, combinatorial group theory, etc. In fact, there are probably more people working in these hybrid fields now than are working in "pure" combinatorics.
posted by Frobenius Twist at 11:44 AM on September 21, 2011

This seems wayyyyyyyyy out of my brain power, but combinatorics was always described as 'math for English majors' at my undergrad.
posted by sperose at 11:53 AM on September 21, 2011

I find it terribly convenient that when people ask what I do, I can say "counting". Granted, it does little to disabuse them of false notions as to what math is about, but I can give them some small or easy to explain example and then they smile and nod and stop trying to tell me how I must be very good at calculus and how they were rubbish at math in school. If they actually care about what I'm saying, I can draw some pictures and/or send them to Wikipedia. (Granted, my mother read the wiki article and basically said, "Aha! You count things.")
posted by hoyland at 11:58 AM on September 21, 2011 [1 favorite]

When I read posts like this, I very intensely regret having stopped at a math minor.
posted by jeather at 12:13 PM on September 21, 2011

combinatorics was always described as 'math for English majors' at my undergrad.

I'm the type of weirdo who reads Séminaire Bourbaki for fun, but their initial idea about combinatorics was flat out wrong. Combinatorics is all of three pages in the Éléments de mathématique because they had the idea that algebraic geometry, or maybe algebraic topology, was the future, or at least the only thing worth carrying forward into the future.

It's all about the computers now, Nicolas.
posted by twoleftfeet at 12:22 PM on September 21, 2011

It's been a while since I studied the subject so please correct me if I'm wrong, but my understanding was that, to find the best solution for problems with real world complexity "Big enough" usually involves converting all available matter on the planet/solar system/galaxy/universe into a single computer, and then letting it run until the universe ends.

Well, I'm a pure mathematician, so I don't worry so much about actual implementation details...

(I also don't know how big is too big these days. A fast search says that my university is offering a little under 3000 courses this semester. So, your graph will have 3000 nodes. This seems pretty small in the grand scheme of things. And it's likely to be pretty sparse---many classes won't have overlaps, so that will make the graph more tractable to deal with. My guess is running an algorithm to color that graph is totally doable on a desktop machine. Certainly, something like the greedy algorithm is fast, although it doesn't always produce optimal colorings. But if you want good-enough, then it's totally doable. Maybe a computer scientists/more applied mathematician will chime in with actual knowledge.)
posted by leahwrenn at 12:33 PM on September 21, 2011

Some people look at a problem, see that it's difficult, and say "Well, instead of answering this one question, let's try answering an infinite number of questions at the same time. Maybe that will be easier." These are the kind of people who come up with generating functions.
posted by benito.strauss at 12:48 PM on September 21, 2011 [1 favorite]

I'm in algebraic combinatorics! (Sometimes it's more like combinatorial algebra, though.) A big part of what I've been involved with has leaned heavily on computers to work out examples beyond what anyone could hope to do by hand, and then look through 'experimental data' for theorems that should be proved. And then, with luck, actually prove them.

Lots of interesting real-world combinatorial problems are totally attackable. In fact, the biggest non-government funder for graph theorists for years and years was Bell Labs, who were using lots of combinatorial results to improve their telephone networks. And now there's piles of interesting combinatorial work to be done on mining social network data and genomics. So it's a very applicable field, and one where computers are really essential to our understanding.
posted by kaibutsu at 1:22 PM on September 21, 2011

Btw, I work a bit on the Combinat extension for the Sage computer algebra system. Combinat is full of research-grade combinatorial functions, which are steadily included into main sage. Meaning that Sage kicks ass at combinatorics, and is worth checking out if you're interested in this stuff. It's free!
posted by kaibutsu at 1:23 PM on September 21, 2011 [2 favorites]

Expanding on what leahwrenn wrote, my favorite real world use of graph coloring is the following:

My friends and I were at a bar, getting ready to do bar trivia. The group was large enough that we wanted to split into two groups, but there were people who had to be together (couples, or new people who only were affiliated to the group through one person, etc.) and people who couldn't be together (specifically two people that just didn't like a particular person).

So, I grouped everyone who had to be in groups together as vertices, and I modeled that one negative relation as an edge between two groups. Ended up that there were four vertices and one edge, so coloring that graph with two colors (because we wanted to split into two groups) could be done in a lot of ways, and I imposed the additional constraint that the number of people in each group should be close. If we assign a weight to each vertex given by the number of people in that vertex, then what we want is a coloring where each color has approximately the same total weight. The problem was super easy to solve in this case, on a napkin (as is traditional).

This tempted me to go further and try to figure out an algorithm for coloring a weighted graph so that you minimize the range of weights in each color, but that kinda stalled out. (I suspect that this is actually an NP problem, but I've never really studied complexity, so I've no idea how to prove it.)

Anyways, it's one of the few times in my life that I've been sitting around and unexpectedly needed to make up a graph to solve a real-world problem.
posted by TypographicalError at 3:43 PM on September 21, 2011 [3 favorites]

As an aside, there is also the Robertson–Seymour theorem which says that any infinite list of graphs contains two graphs X and Y such that X is a minor of Y, i.e. you may arrive at X by deleting or contracting edges of Y. Btw, the proof is 500 pages!

In consequence, you may characterize any minor closed property of graphs by a finite list of forbidden minors, kinda like Kuratowski's theorem characterized planar graphs, except now you may ask crazy questions like "knotless embedding in three-dimensional space".

For any graph X, there is an O(n^3) algorithm to identify graphs that have X as a minor, meaning any minor closed property has an O(n^3) algorithm. woo! Btw, there are actually linear time algorithms for testing planarity, but they're kinda bitchy.
posted by jeffburdges at 4:44 PM on September 21, 2011

Heh. I was just thinking about posting a combinatorics problem to AskMe. So here it is:

I've been playing a game called Spot It with my kids. The game consists of a set of circular cards, each with eight symbols on it, the symbols drawn from a bank of perhaps twenty or so different ones. Allegedly - I haven't tested this! - any pair of cards has one, and only one symbol in common. You play the game by finding the matching symbol on a pair of cards, then replacing one card with a new one and so on.

Clearly the deck of possible cards is defined by m, the number of symbols per card; n, the number of different symbols in the symbol bank; and c, the number of cards that can use any particular symbol - it wouldn't be a good game if every card had the same symbol!

My question is: given values for m, n, and c, how many cards can be made so that any card has precisely one symbol in common with any other card?
posted by Joe in Australia at 4:56 PM on September 21, 2011

Btw, I work a bit on the Combinat extension for the Sage computer algebra system.

I think for this we must all thank you and curse you simultaneously. Or I should just learn not to waste so much time fighting with sage.
posted by hoyland at 5:00 PM on September 21, 2011

That's where combinatorics on words comes in.

There's a review of some book on combinatorics of words, written by someone who does "recreational linguistics" (palindromes, anagrams, that sort of thing), that basically complains that combinatorics on words does not deal with actual words but just strings of letters. I wish I could find it right now.
posted by madcaptenor at 5:54 PM on September 21, 2011

It's worth mentioning that for pretty much any subject area in pure math, you can add "combinatorial" in front of it and get an active area of research -- combinatorial algebraic geometry, combinatorial representation theory, combinatorial group theory, etc. In fact, there are probably more people working in these hybrid fields now than are working in "pure" combinatorics.

And of course there are active research areas generated by putting any word in front of "combinatorics", as well. There's analytic combinatorics (my area), which is really just a dignified word for generatingfunctionology, and can be abbreviated rather unfortunately to anal. comb. Also algebraic combinatorics, geometric combinatorics, topological combinatorics...

The question of how many ways you can generate names of areas of mathematics by combining a few basic words is, of course, a combinatorial problem.
posted by madcaptenor at 5:59 PM on September 21, 2011 [3 favorites]

Joe, Your card decks are probably finite projective planes, meaning :
(1) Any two symbols (points) determine a unique card (line),
(2) Any two cards (lines) have exactly one symbol (point) in common, and
(3) There are four symbols (points), no three of which belong to the same card (line).

We say the number of symbols (points) on each card (line) is the order of the projective plane. There are projective planes of all prime power orders but it's a major open conjecture whether the order is always a prime power.

You obviously didn't specify either (1) or (3) in your description, but probably you have four cards, no three of which contain a common symbol, thus giving the dual condition for (3). I'd imagine (1) and (3) appear elsewhere in the game's rules, meaning you'll need desks who's cards have 3, 4, 5, 7, 8, 9, 11, 13, 16, etc. symbols.
posted by jeffburdges at 7:23 PM on September 21, 2011

And googling "Is Spot it a projective plane?" yields a mathoverflow which yields an article in French.
posted by jeffburdges at 7:25 PM on September 21, 2011

It's worth mentioning that for pretty much any subject area in pure math, you can add "combinatorial" in front of it and get an active area of research

I took this as a challenge and a few experiments with Google showed it to be generally true. The most obscure one I could come up with was "combinatorial differential equations", which I could only find as a section in a book. Can anyone go more obscure?
posted by benito.strauss at 7:26 PM on September 21, 2011

There are definitely differential equations who's solutions are found by viewing them as a generating function and making counting arguments. Any such trick cuts both ways. Check out Gian-Carlo Rota's book on Differential Equations.

Also, "combinatorial non-commutative geometry" has no google hits when quoted, while "combinatorial symplectic geometry" has only four, two with scare quotes.
posted by jeffburdges at 7:42 PM on September 21, 2011

May I submit "combinatorial combinatorics"?

The term "combinatorial functional analysis" has very few (mathematical) ghits, but on inspection of those few, I find that the topic is not so obscure (relative to functional analysis), just not usually named this way.

Here's my favourite fact about graph colouring: If you can 3-colour all 3-colourable graphs — well, actually, if you can extend any partial 3-colouring of a 3-colourable graph into a complete 3-colouring of that graph — then you can compute any function (with finite domain and range).
posted by stebulus at 8:10 PM on September 21, 2011

As an aside, there is a trend for combinatorics to mean computations that don't fit well into any better understood or more direct theory. I donno if it's really productive describing Shelah's Classification theory as combinatorial though.
posted by jeffburdges at 8:41 PM on September 21, 2011

hoyland: I find it terribly convenient that when people ask what I do, I can say "counting".

I hope you're well paid for this service, but I can't help but imagine you in a cape and felt fangs. Do you by any chance have a vaguely Eastern European accent?
posted by sneebler at 9:09 PM on September 21, 2011

My dissertation was dedicated to the Count. He was my first math teacher.
posted by madcaptenor at 9:12 PM on September 21, 2011 [1 favorite]

Everything I need to know about combinatorics I learned on Square One TV.
posted by IndigoRain at 12:42 AM on September 22, 2011 [1 favorite]

mathoverflow.net fun : topple height of randomly stacked bricks.
posted by jeffburdges at 9:59 PM on October 6, 2011 [1 favorite]