Mathematics for informatics and computer science

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