Notes on Counting Tree Structures

A few months ago, I gave a talk at our chair's seminar on counting tree-like structures. Here, I am sharing my notes and the accompanying slides.

Introduction

The idea of these notes is to introduce tree counting to computer scientists by combining extraordinary existing expositions, each focusing on a particular subtopic needed, in a consistent fashion. To do so, we let ourselves be guided by the following classical problems in combinatorics.

• Given three distinct dice, what is the probability that their eyes sum to ten?
• How many ways are there of making change for $1?
• What is the number of necklaces that can be constructed from five beads available in three distinct colors?
• In how many ways can the corners of a square be colored?
• How many trees with a given number of nodes are there?

Indeed, by addressing these questions one by one, we build up to the Pólya enumeration theorem [Pólya, 1937]¹, one of the most powerful results in enumerative combinatorics, and used here to enumerate the number of trees with given node degree. Along the way, we recall generating functions, some group theory, Burnside’s lemma, and Otter’s dissimilarity characteristic theorem.

The exposition of Pólya’s enumeration theorem follows Tucker [1974]². For counting trees, we rely on Harary and Palmer [1973]³. Additional helpful resources, besides the ones stated in the main text below, include Riordan [1958]⁴, Harary [1969]⁵, Shapiro [1973]⁶, Judson [2022]⁷.

... continued in the pdf linked above.

References