Mathematics for Informatics and Computer Science

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