Integer partitions and the Arctic Circle theorem

Goal:

How many ways are there to exchange one Euro into spare change (using 1, 2, 5, 10 and 50 cent coins)? This classical problem, which has been solved a long time ago by Leonhard Euler, gives a glimpse into one of the most fascinating topics of discrete mathematics: Integer partitions. Mathematically speaking, a partition of a positive integer n is a sequence of positive integers such that their sum is n. For example, the sequence 1,2,2 is a partition for 5. The number of all such partitions grows very fast (for example, there are roughly 200 million ways to partition the integer 100), which is why computing all of them is not feasible for large integers. In this project, we first implement simple algoritms which randomly generate a partition (with and without constraints) and will then visualize the so called arctic circle theorem, involving tilings of so called Aztec diamonds. As a warmup, the money exchange problem can be treated as well.

Schedule: To be determined with the student(s).

Supervisors: Simon Campese

Difficulty level: Introductory

Tools: Programming can be done in C/C++, Python, R, Matlab/Octave, Wolfram Mathematica, Maple etc., depending on the knowledge of the student.

Results: To be completed at the end of the project.

FSTC -- University of Luxembourg