Mathematics for Informatics and Computer Science (ISTE)
Format: PDF / Kindle (mobi) / ePub
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.
denominator of F(x) is expressed as 1 – x – x 2 = (1 – ϕx)(1 – ϕ’x). F(x) remains to be expressed in the form of simple fractions: F(x) = x / (1 – x – x 2) = A / (1 – ϕx) + B / (1 – ϕ'x) By identification, we find: F(x) = 1 ⎛ 1 1 ⎞ 1+ 5 1− 5 − ⎜ ⎟ with ϕ = and ϕ ' = 5 ⎝ 1− ϕ x 1− ϕ ' x ⎠ 2 2 We can now progress, because: 1 / (1 – ϕx) = 1 + ϕx + ϕ2x2 + ϕ3x3 + … The coefficient of the term in xn is: u(n) = 1 (ϕ n − ϕ ' n ) 5 which is the explicit form of u(n). The inconvenience of this method
number of words of n characters, made from the four letters a, b, c and d, and not having present blocks of two letters ab or ba. The number of those words that begin with a or b is called xn and those beginning with c or d are called yn. a) Calculate z0, z1 and z2. z0 = 1 (is the empty word), z1 = 4, and for n = 2, z2 = 14. Actually there are 2 ways of making words of 2 characters from a four-letter alphabet, but in this case we have to remove the two forbidden words ab and ba. 4 b) Starting
associated with the number of solutions to this equation is: (1 + x + x2 + …)(1 + x2 + x4 + …)(1 + x3 + x6 + …) = 1 (1− x)(1− x 2 )(1− x3 ) The coefficient of the term in xK in the development of this fraction gives the number of solutions to the initial problem. 7.3.8. Exercise 8: other applications of the method using generating functions a) What is the number of ways of taking 16 objects out of categories, with at least two objects from each category? This question can be dealt with
number n in the form of a product of k prime numbers: n = p1a1 p2a2 … pkak , and take the set of n numbers between 1 and n as set E, hence S0 = n. Then let us define k properties of these numbers: property i, with i between 1 and k, means that the number concerned is divisible by the prime number pi that intervenes in the decomposition of n. The objective is to find the numbers that have no properties: these are all the prime numbers that are lower than or equal to n. Numbers with property 1 are
present in a list of numbers . 2.3.8. Words of length n based on 0 and 1 without any block of 1s repeated . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.9. Programming: classification of applications of a set with n elements in itself following the form of their graph . . . . . . . . . . . . . . 2.3.10. Individuals grouped 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . 35 . . . . . 37 . . . . . . . . . . 39 42 Chapter 3. Enumerations in Alphabetical Order . . . .