Combinatorics, Week 5
February 22, 2017

For this meeting, we will work together some counting problems involving non-intersecting arcs.

I have prepared some hand notes on various approaches to counting non-intersecting arcs:

• Week-4-Combinatorics
• Week-5-Combinatorics

The second set of notes concerns counting “diagonal dissections” of an n-gon: How many ways can we cut an n-gon into k+1 regions?

One can look up dissections in The On-Line Encyclopedia of Integer Sequences:

• a033282: The number of diagonal dissections of a convex n-gon into k+1 regions

In particular, I learned from this entry about a new book of interest to us. Section 5.8 (pp115-122) of this book considers dissections of an n-gon:

• 2015 Petersen - Eulerian numbers

The author easily obtains our counts by an advanced use of generating functions. Perhaps we’ll be able to understand this calculation later in the semester.

These numbers have an interpretation as the face counts of a polytope:

• Associahedron