9
$\begingroup$

I am interested in specific examples and applications of enumerative combinatorics in Computer Science -- concrete problems in this field that make explicit use of the concepts and ideas from combinatorics. Are there any good references that you can point me to (books, lectures, ...)?

$\endgroup$
1

5 Answers 5

6
+25
$\begingroup$

A little treasure is the 30 years old Mathematics for the Analysis of Algorithms by D.E. Knuth and D.H. Greene.

  • From the preface: ... Much of the material is drawn from the starred sections of The Art of Computer Programming, Volume 3.

    Analysis of algorithms, as a discipline, relies heavily on both computer science and mathematics. This report is a mathematical look at the synthesis - emphasizing the mathematical perspective, but using motivation and examples from computer science.

    It covers binomial identities, recurrence relations, operator methods and asymptotic analysis, ...

Many years ago when I studied computer science I was fascinated about the cool Cookie Monster, used to analyse hashing and introduced in section 3.1. In fact nearly each section from this book we've studied in a combinatorics seminar had this wow - effect.

$\endgroup$
3
  • $\begingroup$ Hello @MarkusScheuer, I see on your profile that you work in Austria and are an expert in combinatorics. Could you please give me some bibliographic references in German language? Thank you!. $\endgroup$ Sep 26, 2016 at 20:07
  • 1
    $\begingroup$ @DarioGutierrez: Very helpful long time ago was Einführung in die Kombinatorik (2 vols) by Max Jeger. I also like Kombinatorik I, II by Martin Aigner. I also heartily recommend the scripts of Markus Fulmek and Christian Krattenthaler. Regards, $\endgroup$
    – epi163sqrt
    Sep 27, 2016 at 10:27
  • 1
    $\begingroup$ Excellent! thank you very much! :) $\endgroup$ Sep 27, 2016 at 10:53
4
$\begingroup$

A very attractive book, with a virtuous teaching and excellent references on this topic is "Combinatorial Enumerative" (in Spanish), written by the mathematician of Costa Rica, Eduardo Piza Volio, Editorial of the University of Costa Rica (2003). I attached bibliography in which there are other references.

enter image description here

$\endgroup$
3
4
$\begingroup$

Maybe you can help this book:

Enumerative Combinatorics by Richard P. Stanley Download as pdf

Other interesting books:

Principles and Techniques in Combinatorics by Chen Chuan-Chong and Koh Khee-Meng More info - Download as pdf

Combinatorics and Graph Theory (2nd edition) by John Harris, Jeffry L. Hirst, and Michael Mossinghoff - More info - Download as pdf

Combinatorics by RUSSELL MERRIS, California State University, Hayward Download as pdf

$\endgroup$
2
$\begingroup$

A trick that I've been employing on several occasions is ternary number base enumeration:

Quite a limited scope, but very useful.

$\endgroup$
2
$\begingroup$

The emphasis is on enumeration rather than counting if I understand the question correctly. The perfect match would be the combstruct package that is included with Maple. This software is a companion to the book Analytical Combinatorics by Flajolet and Sedgewick, which is the canonical text and basically provides a map of future computer science research for decades to come. Highly recommended. Computer science has a particular focus on trees and combstruct really shines here, providing total enumeration as well as generating functions and functional equations. The landmark paper by Flajolet et al. on random mapping statistics (which are closely related to the labeled tree function) is discussed at this MSE link. The Maple package is used the following MSE combstruct link, I and this MSE combstruct link, II. The book Analytical Combinatorics is unprecedented in that it pioneered the use of complex variable methods to treat generating functions that arise from species theory and the folklore theorem of combinatorial enumeration (providing instant translation from species equations to generating functions), thereby putting an emphasis on unifying combinatorial methods with complex variable techniques. Another relevant early text is the book Graphical Enumeration by Harary and Palmer which contains many results on labeled and unlabeled trees as well as accessible presentations of the Polya Enumeration Theorem and of Power Group Enumeration. Finally a classic contender for the enumeration of unlabeled trees is the NAUTY package by McKay, which was used at this MSE NAUTY link. (Use Pruefer codes for labeled trees.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.