Mathematics for Informatics and Computer Science E-Book

Pierre Audibert

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 1255

Veröffentlichungsjahr: 2013

Beschreibung

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.

Leseprobe

Table of Contents

General Introduction

Chapter 1: Some Historical Elements

1.1. Yi King

1.2. Flavor combinations in India

1.3. Sand drawings in Africa

1.4. Galileo’s problem

1.5. Pascal’s triangle

1.6. The combinatorial explosion: Abu Kamil’s problem, the palm grove problem and the Sudoku grid

PART 1: Combinatorics

Part 1: Introduction

Chapter 2: Arrangements and Combinations

2.1. The three formulae

2.2. Calculation of Cnp, Pascal’s triangle and binomial formula

2.3. Exercises

Chapter 3: Enumerations in Alphabetical Order

3.1. Principle of enumeration of words in alphabetical order

3.2. Permutations

3.3. Writing binary numbers

3.4. Words in which each letter is less than or equal to the position

3.5. Enumeration of combinations

3.6. Combinations with repetitions

3.7. Purchase of P objects out of N types of objects

3.8. Another enumeration of permutations

3.9. Complementary exercises

3.10. Return to permutations

3.11. Gray code

Chapter 4: Enumeration by Tree Structures

4.1. Words of length n, based on N letters 1, 2, 3,…, N, where each letter is followed by a higher or equal letter

4.2. Permutations enumeration

4.3. Derangements

4.4. The queens problem

4.5. Filling up containers

4.6. Stack of coins

4.7. Domino tiling a chessboard

Chapter 5: Languages, Generating Functions and Recurrences

5.1. The language of words based on two letters

5.2. Domino tiling a 2×n chessboard

5.3. Generating function associated with a sequence

5.4. Rational generating function and linear recurrence

5.5. Example: routes in a square grid with rising shapes without entanglement

5.6. Exercises on recurrences

5.7. Examples of languages

5.8. The exponential generating function

Chapter 6: Routes in a Square Grid

6.1. Shortest paths from one point to another

6.2. n-length paths using two (perpendicular) directions of the square grid

6.3. Paths from O to B(n, x) neither touching nor crossing the horizontal axis and located above it

6.4. Number of n-length paths that neither touch nor cross the axis of the adscissae until and including the final point

6.5. Number of n-length paths above the horizontal axis that can touch but not cross the horizontal axis

6.6. Exercises

Chapter 7: Arrangements and Combinations with Repetitions

7.1. Anagrams

7.2. Combinations with repetitions

7.3. Exercises

7.4. Algorithms and programs

Chapter 8: Sieve Formula

8.1. Sieve formula on sets

8.2. Sieve formula in combinatorics

8.3. Examples

8.4. Exercises

8.5. Extension of sieve formula

Chapter 9: Mountain Ranges or Parenthesis Words: Catalan Numbers

9.1. Number c(n) of mountain ranges 2n long

9.2. Mountains or primitive words

9.3. Enumeration of mountain ranges

9.4. The language of mountain ranges

9.5. Generating function of the C2nn and Catalan numbers

9.6. Left factors of mountain ranges

9.7. Number of peaks of mountain ranges

9.8. The Catalan mountain range, its area and height

Chapter 10: Other Mountain Ranges

10.1. Mountain ranges based on three lines

10.2. Words based on three lines with as many rising lines as falling lines

10.3. Example 1: domino tiling of an enlarged Aztec diamond

10.4. Example 2: domino tiling of half an Aztec diamond

10.5. Mountain ranges based on three types of lines

10.6. Example 3: movement of the king on a chessboard

Chapter 11: Some Applications of Catalan Numbers and Parenthesis Words

11.1. The number of ways of placing n chords not intersecting each other on a circle with an even number 2n of points

11.2. Murasaki diagrams and partitions

11.3. Path couples with the same ends in a square grid

11.4. Path couples with same starting point and length

11.5. Decomposition of words based on two letters as a product of words linked to mountain ranges

Chapter 12: Burnside’s Formula

12.1. Example 1: context in which we obtain the formula

12.2. Burnside’s formula

12.3. Exercises

Chapter 13: Matrices and Circulation on a Graph

13.1. Number of paths of a given length on a complete or a regular graph

13.2. Number of paths and matrix powers

13.3. Link between cyclic words and closed paths in an oriented graph

13.4. Examples

Chapter 14: Parts and Partitions of a Set

14.1. Parts of a set

14.2. Partitions of a n-object set

Chapter 15: Partitions of a Number

15.1. Enumeration algorithm

15.2. Euler formula

15.3. Exercises

Chapter 16: Flags

16.1. Checkered flags

16.2. Flags with vertical stripes

Chapter 17: Walls and Stacks

17.1. Brick walls

17.2. Walls of bricks made from continuous horizontal rows

17.3. Heaps

17.4. Stacks of disks

17.5. Stacks of disks with continuous rows

17.6. Horizontally connected polyominos

Chapter 18: Tiling of Rectangular Surfaces using Simple Shapes

18.1. Tiling of a 2×n chessboard using dominos

18.2. Other tilings of a chessboard 2×n squares long

18.3. Tilings of a 3×n chessboard using dominos

18.4. Tilings of a 4×n chessboard with dominos

18.5. Domino tilings of a rectangle

Chapter 19: Permutations

19.1. Definition and properties

19.2. Decomposition of a permutation as a product of disjoint cycles

19.3. Inversions in a permutation

19.4. Conjugated permutations

19.5. Generation of permutations

19.6. Properties of the alternating group An

19.7. Applications of these properties

19.8. Exercises on permutations

PART 2: Probability

Part 2: Introduction

Chapter 20: Reminders about Discrete Probabilities

20.1 And/or in probability theory

20.2. Examples

20.3. Total probability formula

20.4. Random variable X, law of X, expectation and variance

20.5. Some classic laws

20.6. Exercises

Chapter 21: Chance and the Computer

21.1. Random number generators

21.2. Dice throwing and the law of large numbers

21.3. Monte Carlo methods for getting the approximate value of the number π

21.4. Average value of a random variable X, variance and standard deviation

21.5. Computer calculation of probabilities, as well as expectation and variance, in the binomial law example

21.6. Limits of the computer

21.7. Exercises

21.8. Appendix: chi-squared law

Chapter 22: Discrete and Continuous

22.1. Uniform law

22.2. Density function for a continuous random variable and distribution function

22.3. Normal law

22.4. Exponential law and its link with uniform law

22.5. Normal law as an approximation of binomial law

22.6. Central limit theorem: from uniform law to normal law

22.7. Appendix: the distribution function and its inversion – application to binomial law B(n, p)

Chapter 23: Generating Function Associated with a Discrete Random Variable in a Game

23.1. Generating function: definition and properties

23.2. Generating functions of some classic laws

23.3. Exercises

Chapter 24: Graphs and Matrices for Dealing with Probability Problems

24.1. First example: counting of words based on three letters

24.2. Generating functions and determinants

24.3. Examples

Chapter 25: Repeated Games of Heads or Tails

25.1. Paths on a square grid

25.2. Probability of getting a certain number of wins after n equiprobable tosses

25.3. Probabilities of certain routes over n moves

25.4. Complementary exercises

25.5. The gambler’s ruin problem

Chapter 26: Random Routes on a Graph

26.1. Movement of a particle on a polygon or graduated segment

26.2. Movement on a polyhedron

26.3. The robot and the human being

26.4. Exercises

Chapter 27: Repetitive Draws until the Outcome of a Certain Pattern

27.1. Patterns are arrangements of K out of N letters

27.2. Patterns are combinations of K letters drawn from N letters

27.3. Wait for patterns with eventual repetitions of identical letters

27.4. Programming exercises

Chapter 28: Probability Exercises

28.1. The elevator

28.2. Matches

28.3. The tunnel

28.4. Repetitive draws from a box

28.5. The sect

28.6. Surfing the web (or how Google works)

PART 3: Graphs

Part 3: Introduction

Chapter 29: Graphs and Routes

29.1. First notions on graphs

29.2. Representing a graph in a program

29.3. The tree as a specific graph

29.4. Paths from one point to another in a graph

Chapter 30: Explorations in Graphs

30.1. The two ways of visiting all the vertices of a connected graph

30.2. Visit to all graph nodes from one node, following depth-first traversal

30.3. The pedestrian’s route

30.4. Depth-first exploration to determine connected components of the graph

30.5. Breadth-first traversal

30.6. Exercises

30.7. Returning to a depth-first exploration tree

30.8. Case of directed graphs

30.9. Appendix: constructing the maze (simplified version)

Chapter 31: Trees with Numbered Nodes, Cayley’s Theorem and Prüfer Code

31.1. Cayley’s theorem

31.2. Prüfer code

31.3. Randomly constructed spanning tree

Chapter 32: Binary Trees

32.1. Number of binary trees with n nodes

32.2. The language of binary trees

32.3. Algorithm for creation of words from the binary tree language

32.4. Triangulation of polygons with numbered vertices and binary trees

32.5. Binary tree sort or quicksort

Chapter 33: Weighted Graphs: Shortest Paths and Minimum Spanning Tree

33.1. Shortest paths in a graph

33.2. Minimum spanning tree

Chapter 34: Eulerian Paths and Cycles, Spanning Trees of a Graph

34.1. Definition of Eulerian cycles and paths

34.2. Euler and Königsberg bridges

34.3. Number of Eulerian cycles in a directed graph, link with directed spanning trees

34.4. Spanning trees of an undirected graph

Chapter 35: Enumeration of Spanning Trees of an Undirected Graph

35.1. Spanning trees of the fan graph

35.2. The ladder graph and its spanning trees

35.3. Spanning trees in a square network in the form of a grid

35.4. The two essential types of (undirected) graphs based on squares

35.5. The cyclic square graph

35.6. Examples of regular graphs

Chapter 36: Enumeration of Eulerian Paths in Undirected Graphs

36.1. Polygon graph with n vertices with double edges

36.2. Eulerian paths in graph made up of a frieze of triangles

36.3. Algorithm for Eulerian paths and cycles on an undirected graph

36.4. The game of dominos

36.5. Congo graphs

Chapter 37: Hamiltonian Paths and Circuits

37.1. Presence or absence of Hamiltonian circuits

37.2. Hamiltonian circuits covering a complete graph

37.3. Complete and antisymmetric directed graph

37.4. Bipartite graph and Hamiltonian paths

37.5. Knights tour graph on the N×N chessboard

37.6. de Bruijn sequences

APPENDICES

Appendix 1: Matrices

A1.1. Notion of linear application

A1.2. Bijective linear application

A1.3. Base change

A1.4. Product of two matrices

A1.5. Inverse matrix

A1.6. Eigenvalues and eigenvectors

A1.7. Similar matrices

A1.8. Exercise

A1.9. Eigenvalues of circulant matrices and circular graphs

Appendix 2: Determinants and Route Combinatorics

A2.1. Recalling determinants

A2.2. Determinants and tilings

A2.3. Path sets and determinant

A2.4. The hamburgeer graph: disjoint cycles

Bibliography

Index

First published 2010 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Adapted and updated from three volumes Combien ? Mathématiques appliquées à l’informatique 1, 2, 3 published 2008 in France by Hermes Science/Lavoisier (c) LAVOISIER 2008

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUKJohn Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.iste.co.ukwww.wiley.com

© ISTE Ltd 2010

The rights of Pierre Audibert to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Audibert, Pierre, 1941-

Mathematics for informatics and computer science / Pierre Audibert.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-196-4

1. Computer science--Mathematics. I. Title.

QA76.9.M35A83 2010

004.01'51--dc22

2010028591

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-196-4

General Introduction

Combinatorics and all the fields deriving from it — the probabilities and graph theories — are no longer peripheral phenomena, at the edge of pure mathematics. We can even consider combinatorics as bringing a breath of fresh air into the universe of theory. Indeed it has its own style of demonstrations, which often require more tricks and common sense than the systematic application of the mainstream mathematical theories. It is also an introduction in a concrete manner of some abstract algebraic tools such as matrices and determinants. The recent development of combinatorics also results from the worldwide emergence of informatics, which offers unlimited possibilities of practice and experimentation, i.e. either to check or anticipate theoretical results, or to solve problems that theory cannot solve. Combinatorics associated with counting and enumerating allows us to encode events in words, made of numbers or letters, which brings the field closer to linguistics. The word dictionaries obtained can in turn be illustrated on computer screen through complex shapes and patterns, such as the new hieroglyphs, which are able to strike the imagination and stimulate the artistic interpretation.

Combinatorics is first studied in science classes at high school, where it is associated with the calculation of probabilities, and recently, with graphs theory. The calculation of the probabilities and its algorithms is also a favorite field used in the entrance examination for major business schools. On the other side of the coin, the number of high-level publications has multiplied in specialized journals, which are only accessible to a few. This book falls between the two camps. It gradually moves from basic introductory sections to the latest theoretical developments in the field, illustrated by numerous examples.1

This book targets students and researchers, and more broadly knowledgeable amateurs. High school and preparatory school teachers will find here many useful examples and exercises. Depending on the theoretical level of the audience, some readers will prefer to focus on the algorithms, or even the graphic visuals, others will concentrate on the algebraic or combinatorial implementations. The aim of this book is to achieve a global overview of the state of the art in the field.

About the algorithms and programs

One of the specific aspects of this book is to provide a large number of algorithms and programs, all explained in full detail. The programs are designed in abridged versions using C language, and they are easily adaptable to other similar languages such as Pascal or Basic. Mathematics enthusiasts will need to convert these programs directly into a scientific language such as Mathematica if they want to benefit from the graphic functions. In order to learn C programming and SDL graphics, I recommend that readers visit my website, created within the framework of LIASD (Laboratoire d’informatique avancée de Saint-Denis, Paris 8 University): www.ai.univ-paris-8.fr/~audibert/. Under the heading "Book Programs", we give many programs present in this book. They are in full programs, written in C with SDL graphical help, with their codes as well as their executable files.2

Structure of the book

The book is divided into three parts:

− Part 1: Combinatorics;

− Part 2: Probability;

− Part 3: Graphs.

Although these three parts can be read separately, they are connected by counting and enumerating algorithms, following the same reading line, i.e. the concept of generating functions3. Despite the large number of subjects studied, this book does not claim to be exhaustive. Interested readers will find more details in [TUC 02], notably on games based on graphs, in [LEN 03] on mathematical linguistics, and in [STA 01] or [LOT 97] for a deeper theoretical vision. Let us not forget to mention [SLO 95], the global reference in the field of integer sequences, or the pioneering book by [COM 70].

Acknowledgements

I want to thanks my colleagues and friends, particularly F. Belhadj, P. Chibaudel, S. El Baz, C. Fer, P. Greussay, C. Lenormand, I. Saleh, H. Wertz, who helped me a lot. I also wish to thank the hundred or so students who wrote their MD or PhD theses under my supervision. They have allowed me to work on a diversity of subjects, but always on an algorithmic basis: ranging from my first student R. Abdoul (on sand avalanches) to my latest I. Mazouzi (about the Chinese theorem), to the other students who explored combinatorial problems and whose works are mentioned in this book: H. Arfa, A. Fathi, N. Grassa, N. Rifaai, Y. Naciri.

1. In this respect, we used the work by Graham, Knuth and Patashnik, Concrete Mathematics [GRA 90] as a source of inspiration and a model.

2. In order to learn C programming and SDL graphics, the "happy few" who read French will find a brief introduction about their use, in my web pages. Under the rubric "Education", where IT and mathematics (level 1, L1) and algorithmics (Level 2, L2) courses are listed, in chapter entitled "Graphics SDL: second layer", two functions of basic graphics are listed: putpixel and getpixel (formerly called peek and poke), as well as the functions making it possible to draw lines and circles. Readers will also learn the way to draw a segment with arrows, which is highly necessary for drawing graphs. Should the need arise, the chapters dealing with recursivity and linked lists will enable easy comprehension of these more complex concepts. In "Complementary Works", some mathematical games, among others, are explained (such as Marienbad, Instant Insanity, Planarity) with their complete programmings. For algorithmic enthusiasts in general, see the following books for further detail: [AHO 87], [BER 91], [COR 02], [SED 91].

3. For a full understanding of generating functions refer to [WIL 94].

PART 1

Combinatorics

Part 1

Introduction

On first analysis, combinatorics can be summarized in three formulae, and this is the aim of Chapter 2. Notably, we will see that the number of combinations of p objects taken out of n objects, without taking into consideration the order in which they are taken, is deduced from the number of arrangements where order comes into play. This is a method that applies in quite a few other circumstances. Other theoretical elements - sieve formula and Burnside’s formula - are presented in Chapters 8 and 11, respectively. The first formula enables us to select, from a set of objects, those that present certain characteristics and count them. The second enables us to group objects that present symmetries by counting only the groups of those that remain identical through these symmetries.

The practical aspect will be added to this theoretical aspect. How can the results obtained be enumerated without forgetting any of them or giving the same result several times in a row? There are two types of algorithms on this subject: namely, an enumeration of results in alphabetical order, created by searching for how to go from one word to the next; and an enumeration by tree structure, where words gradually get longer and longer, becoming the descending branches of the final tree. These two algorithms, developed in Chapters 3 and 4, answer practically all combinatorics problems when programmed on a computer. They will be implemented from the beginning to the end of this book.

Next, the tools necessary for problem-solving are implemented - the concepts of generating functions and recurrence relations that enable us to obtain counting formulae from the results. As we will see in Chapter 5, these concepts are the immediate result of formal series, i.e. they boil down to the syntax of languages. This is nothing other than combinatorics on words, which is nothing other than mathematical linguistics. These methods will be applied in several contexts. First, they will be applied in routes on a square grid (Chapter 6), also called taxicab geometry. This geometric view will then enable us to deal, in a simple way, with what is called arrangements and combinations with repetition, where arrangements with repetition of the same letters are nothing other than anagrams (Chapter 7). Still with this geometric background, we will bring it all together with the notion of mountain ranges, more officially called parenthesis words. This will provide the opportunity to define Catalan numbers, which appear in many circumstances and which, like Fibonacci numbers, are the basic numbers of combinatorics. The versatility of these numbers will be seen in its entirety in Chapters 9, 10 and 11. Finally, even before the part devoted to graphs, the link between word-making and circulation on a graph is evoked in Chapter 13, where a new tool - matrix calculation - appears.

The last chapters apply to specific contexts. Chapter 14 is devoted to set partition, Chapter 15 to number partition. Chapters 16, 17 and 18 deal with concrete examples linked to the idea of flags, stacking and tiling. Finally, Chapter 19 makes use of and develops the notion of permutations.