Combinatorics—Spring 2007

March 2, 2007

Combinatorial versions of Catalans

Wikipedia does a decent job of introducing a few other interpretations of Catalan numbers, and of presenting a couple of combinatorial proofs of the formula for them.

If you want more, Richard Stanley at MIT has a stunning list of combinatorial interpretations. And that list is an addendum to the 66 or so that he gives in one of his books!

February 28, 2007

An even longer proof that there are 2ⁿ subsets of [n]

See Doron Zeilberger's almost-but-not-quite-entirely tongue-in-cheek little article, A new proof that there 2^n ways to toss a coin n times. (Remember to apply the standard bijection between head/tail sequences and subsets of [n].)

(Questions: how many of the things that we've talked about in class is this proof using? And how are its generating functions different from ours?)

February 21, 2007

Quick check

Mathematica agrees with our computations in class:

(The second argument to Series is of the form {variable of expansion, base point for expansion, exponent of highest term included}. Here the variable is t and the base point is 0, so we get a result in terms of powers of (t-0).)

February 16, 2007

Fermat's little theorem

Solutions to Assignment 1 have beeen posted (see link at left). Problem 6 was to prove Fermat's Little Theorem. You might be interested in Tim Gower's essay on why it's a natural result, and two natural proofs of it (one of which is what you most likely did on your homework).

(Note: Tim Gowers is a Fields medalist.)

February 14, 2007

Pascal's triangle, mod n

First, some primes. Mod 2:

Mod 3:

And mod 11:

Finally, compare what happens with a composite, namely, 12:

February 5, 2007

Welcome to Combinatorics!

We will meet on Mondays, Wednesdays, and Fridays at 11:00 a.m. in King 121.

Our main textbook will be Cameron's Combinatorics: Topics, Techniques, Algorithms. See the syllabus for more information.

This website will run a bit like a blog. Important dates will be listed in the column to the left, along with links to assignments (and solutions). Announcements and interesting links will appear in the main body, right here.