Combinatorics Seminar

Negative results in enumerative combinatorics

Miklos Bona

Thursday, October 21st, 2021
5:00 PM - 6:00 PM
Hylan 1106A

When we cannot solve an enumeration problem, we wonder whether we are just missing an easy solution or the problem is indeed di cult. In this talk, we will survey some recent methods that can prove that the generating function of some combinatorially de ned sequences is not rational or not algebraic.

As an application, we will show that the generating function for the num- ber of permutations avoiding a given pattern q is almost never rational. In some cases, we will show that that generating function is not even algebraic. We will also show that six classic families of algebraic generating functions will never be rational. We will conclude will some intriguing open problems.

Event contact: iosevich at gmail dot com