Recently, I came across a nice post on basic combinatorics. It brings back some vague memory from my middle school time when I started to learn very basic stuff related to combinations, permutations, etc. At first, I was not too excited about figuring out those formulae on my own. As time goes by, however, I’ve realized that the intuitive meanings, principles under the hood are incredibly useful and interesting. Counting, or enumerating discrete structures, e.g., sets of elements satisfying certain criteria are fundamental and common problems that we often meet in our daily life. Instead of giving a thorough review of basics of combinatorics which is well beyond the scope of my humble knowledge, I’d like to jot down some things (e.g., facts, problems, etc.) mostly related to practical usage of basic combinatorics. For more details, please refer to standard discrete math books, combinatorics book, etc. I will keep updating this post whenever I find something new and interesting. Constructive comments and suggestions are really appreciated.
Catalan numbers
The n-th Catalan number is defined as: $C_n = \frac{(2n)!}{n!(n+1)!}$. Well, it is another randomly boring formula, isn’ it? It turn out that these numbers have some surprisingly nice properties, particularly if you happen to figure them out on your own. For examples,
+ $C_n$ is the number of Dyck words of length $2n$, with a nice geometrical interpretation as shown in this post.
+ $C_n$ is the number of correct arrangements of $n$ pairs of parentheses. This is followed directly from the definiton of Dyck words above.
+ $C_n$ is the number of possible triangulations of a polygon with $n+2$ vertices. The triangulation problem is a very nice problem itself that you might want to find out more later. Here comes the first question, can you prove this fact? Hint: Try to build a bijection between the set of correct arrangements of $n$ pairs of parentheses with the set of all possible triangulations of a polygon with $n+2$ vertices.
Useful tip: Find a bijection, i.e., a one-one mapping between two countable sets to prove their cardinalities are equal is an useful technique often employed in combinatorics, and general problem solving. Also, by building the mapping between an unknown problem to a problem with well-known solutions, you can easily obtain the solutions of the former without trying to solve it directly (it might be difficult!).