0;115;0c Algorithmic Combinatorics 2024S
RISC JKU

Algorithmic Combinatorics

Mon, 15:30-17:00, S2 046

The lecture will be held in English.

In the course we focus on algorithmic methods for proving identitities related to combinatorics, for example Cassini's identity, trigonometric identities, in general any identity involving functions that are holonomic. A sequence like the Fibonacci sequence is said to be holonomic because it satisfies a certain type of recurrence. Similarly an analytic function is called holonomic if the sequence formed by the coefficients in its Taylor series expansion is holonomic. For example the cosinus and the sinus are holonomic functions. It turns out that we can use this holonomic property to prove identities involving such functions. Also holonomic sequences respectively recurrences satisfy so called closure properties. That is, if sequences f,g resp. functions F,G are holonomic then so is fxg,f+g resp. FxG, F+G. This aspect is what allows for algorithmic proofs of identitites related to holonomic sequences resp. functions.

We will cover topics like


Lecture1

Lecture2

Lecture3

Lecture4

Lecture5

Lecture6

Lecture7

Lecture8

Lecture9


The final exam is scheduled individually with each course participant, and will take place via Zoom. The exam takes 30 minutes and I will ask about certain things that I will mention during the course.

Requirements: Basic knowledge from analysis and linear algebra.

Silviu Radu

Exercises:

Mon, 17:15-18:00, S2 046

Koustav Banerjee