In this course we give an introduction to counting problems and counting complexity. While often in complexity theory we investigate decision problems of the form "Does problem X have a solution?", here we focus on questions of the form "How many solutions does problem X have?". Such questions are motivated for instance by applications in

• statistical physics  - "How many different states are there in some system of particles?",
• probability theory - "How many outcomes of a random experiment contributes to some event in comparison to the overall number of possible outcomes?",
• pattern counting - "How frequent is some pattern in a given biological networks/neural networks/the internet/social network...?" ,
• database theory - "How many answers are there to a given query in a given database?",
•  ...

We cover selected techniques that have been used to analyze the complexity of counting problems and discuss many of these techniques in the context of counting generalized colorings of graphs, for example:

• "How many 3-colorings are there in a given graph?"
• "How many independent sets are there in a given graph?"

(Additional literature for specific lectures will be added after the corresponding lectures.)