Experimental Methods in Combinatorics

Dr. Jay Pantone
Assistant Professor of Mathematics
Marquette University

What number comes next in the sequence
1, 2, 4, 8, 16, 32, … ?

How about
1, 2, 3, 5, 8, 13, … ?

Or maybe
1, 3, 14, 84, 592, 4659, … ?

Many questions in combinatorics have the form “How many objects are there that have size n and that satisfy certain properties?” For example, there are n! permutations (rearrangements) of n distinct objects, there are 2^n binary strings of length n, and the number of sequences of n coin flips that never have two tails in a row is the nth Fibonacci number. The “counting sequence” of a set of objects is the sequence a_0, a_1, a_2, …, where a_n is the number of objects of size n.

As a result of theoretical advances and more powerful computers, it is becoming common to be able to compute a large number of initial terms of the counting sequence of a set of objects that you’d like to study. From these initial terms, can you guess future terms? Can you guess a formula for the nth term in the sequence? Can you guess the asymptotic behavior as n tends to infinity?

Rigorously, you can prove basically nothing from just some known initial terms. But, perhaps surprisingly, there are several empirical techniques that can use these initial terms to shed some light on the nature of a sequence.

As we talk about two such techniques — automated conjecturing of generating functions, and the method of differential approximation — we’ll exhibit their usefulness through a variety of combinatorial topics, including chord diagrams, permutation classes, and inversion sequences.