0;115;0c Algorithmic Combinatorics 2024S

# 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

• Holonmic sequences
• Holonomic functions
• Algorithmic methods for treating identities related to holonomic sequences and functions
• Closure properties
• Main connection between holonomic sequences and holonomic functions
• Formal power series
• Transfer principle

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.

## Exercises:

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

Koustav Banerjee