Tag Archives: combinatorics

From Euler Characteristics to Cohomology (I)

Posted on December 2, 2013 by limsup

[ Warning: this is primarily an expository article, so the proofs are not airtight, but they should be sufficiently convincing. ] The five platonic solids were well-known among the ancient Greeks (V, E, F denote the number of vertices, edges and faces respectively): … Continue reading →

Posted in Notes | Tagged , , , , , , , | Leave a comment

Thoughts on a Problem III

Posted on February 8, 2013 by limsup

I saw an interesting problem recently and can’t resist writing it up. The thought process for this problem was exceedingly unusual as you’ll see later. First, here’s the source: But here’s the full problem (rephrased a little) if you’d rather … Continue reading →

Posted in Thought | Tagged , , , , | Leave a comment

Burnside’s Lemma and Polya Enumeration Theorem (2)

Posted on January 15, 2013 by limsup

[ Acknowledgement: all the tedious algebraic expansions in this article were performed by wolframalpha. ] Counting Graphs One of the most surprising applications of Burnside’s lemma and Polya enumeration theorem is in counting the number of graphs up to isomorphism. … Continue reading →

Posted in Notes | Tagged , , , , , , , , | Leave a comment

Burnside’s Lemma and Polya Enumeration Theorem (1)

Posted on January 13, 2013 by limsup

[ Note: this article assumes you know some rudimentary theory of group actions. ] Let’s consider the following combinatorial problem. Problem. ABC is a given equilateral triangle. We wish to colour each of the three vertices A, B and C by … Continue reading →

Posted in Notes | Tagged , , , , , , , | Leave a comment

Power Series and Generating Functions (IV) – Exponential Generating Functions

Posted on March 26, 2012 by limsup

Note: this article is noticeably more difficult than the previous instalments. The reader is advised to be completely comfortable with generating functions before proceeding. We’ve already seen how generating functions can be used to solve some combinatorial problems. The nice … Continue reading →

Posted in Notes | Tagged , , , , , | 3 Comments

Power Series and Generating Functions (III) – Partitions

Posted on March 19, 2012 by limsup

One particularly fruitful application of generating functions is in partition numbers. Let n be a positive integer. A partition of n is an expression of n as a sum of positive integers, where two expressions are identical if they can be obtained from each … Continue reading →

Posted in Notes | Tagged , , , , , , | Leave a comment

Power Series and Generating Functions (II): Formal Power Series

Posted on February 19, 2012 by limsup

For today’s post, we shall first talk about the Catalan numbers. The question we seek to answer is the following. Let n be a positive integer. Given a non-associative operation *, find the number of ways to bracket the expression … Continue reading →

Posted in Notes | Tagged , , , , | Leave a comment

Power Series and Generating Functions (I): Basics

Posted on February 5, 2012 by limsup

[ Background required: basic combinatorics, including combinations and permutations. Thus, you should know the formulae and and what they mean. Also, some examples / problems may require calculus. ] Note: this post is still highly relevant to competition-mathematics. 🙂 To … Continue reading →

Posted in Notes | Tagged , , , , , | Leave a comment