Mathematics for Informatics and Computer Science

How many ways do exist to mix different ingredients, how many chances to win a gambling game, how many possible paths going from one place to another in a network ? To this kind of questions Mathematics applied to computer gives a stimulating and exhaustive answer. This text, presented in three parts (Combinatorics, Probability, Graphs) addresses all those who wish to acquire basic or advanced knowledge in combinatorial theories. It is actually also used as a textbook. Basic and advanced theoretical elements are presented through simple applications like the Sudoku game, search engine algorithm and other easy to grasp applications. Through the progression from simple to complex, the teacher acquires knowledge of the state of the art of combinatorial theory. The non conventional simultaneous presentation of algorithms, programs and theory permits a powerful mixture of theory and practice. All in all, the originality of this approach gives a refreshing view on combinatorial theory.

How many ways do exist to mix different ingredients, how manychances to win a gambling game, how many possible paths going fromone place to another in a network ? To this kind of questionsMathematics applied to computer gives a stimulating and exhaustiveanswer. This text, presented in three parts (CombinatoricsProbability, Graphs) addresses all those who wish to acquire basicor advanced knowledge in combinatorial theories. It is actuallyalso used as a textbook.Basic and advanced theoretical elements are presented throughsimple applications like the Sudoku game, search engine algorithmand other easy to grasp applications. Through the progression fromsimple to complex, the teacher acquires knowledge of the state ofthe art of combinatorial theory. The non conventional simultaneouspresentation of algorithms, programs and theory permits apowerful mixture of theory and practice.All in all, the originality of this approach gives a refreshingview on combinatorial theory.

General Introduction xxiiiChapter 1. Some Historical Elements 1PART 1. COMBINATORICS 17Part 1. Introduction 19Chapter 2. Arrangements and Combinations 21Chapter 3. Enumerations in Alphabetical Order 43Chapter 4. Enumeration by Tree Structures 63Chapter 5. Languages, Generating Functions and Recurrences85Chapter 6. Routes in a Square Grid 105Chapter 7. Arrangements and Combinations with Repetitions119Chapter 8. Sieve Formula 137Chapter 9. Mountain Ranges or Parenthesis Words: Catalan Numbers165Chapter 10. Other Mountain Ranges 197Chapter 11. Some Applications of Catalan Numbers and ParenthesisWords 215Chapter 12. Burnside's Formula 227Chapter 13. Matrices and Circulation on a Graph 253Chapter 14. Parts and Partitions of a Set 275Chapter 15. Partitions of a Number 289Chapter 16. Flags 305Chapter 17. Walls and Stacks 315Chapter 18. Tiling of Rectangular Surfaces using Simple Shapes331Chapter 19. Permutations 345PART 2. PROBABILITY 387Part 2. Introduction 389Chapter 20. Reminders about Discrete Probabilities 395Chapter 21. Chance and the Computer 427Chapter 22. Discrete and Continuous 447Chapter 23. Generating Function Associated with a DiscreteRandom Variable in a Game 469Chapter 24. Graphs and Matrices for Dealing with ProbabilityProblems 497Chapter 25. Repeated Games of Heads or Tails 509Chapter 26. Random Routes on a Graph 535Chapter 27. Repetitive Draws until the Outcome of a CertainPattern 565Chapter 28. Probability Exercises 597PART 3. GRAPHS 637Part 3. Introduction 639Chapter 29. Graphs and Routes 643Chapter 30. Explorations in Graphs 661Chapter 31. Trees with Numbered Nodes, Cayley's Theoremand Prüfer Code 705Chapter 32. Binary Trees 723Chapter 33. Weighted Graphs: Shortest Paths and Minimum SpanningTree 737Chapter 34. Eulerian Paths and Cycles, Spanning Trees of a Graph759Chapter 35. Enumeration of Spanning Trees of an Undirected Graph779Chapter 36. Enumeration of Eulerian Paths in Undirected Graphs799Chapter 37. Hamiltonian Paths and Circuits 835APPENDICES 867Appendix 1. Matrices 869Appendix 2. Determinants and Route Combinatorics 885Bibliography 907Index 911