Cover -- Mathematics for Informatics and Computer Science -- Title Page -- Copyright Page -- 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 -- 1.6.1. Solution to Abu Kamil's problem -- 1.6.2. Palm Grove problem, where N = 4 -- 1.6.3. Complete Sudoku grids -- 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 -- 2.3.1. Demonstrating formulae -- 2.3.2. Placing rooks on a chessboard -- 2.3.3. Placing pieces on a chessboard -- 2.3.4. Pascal's triangle modulo k -- 2.3.5. Words classified based on their blocks of letters -- 2.3.6. Diagonals of a polygon -- 2.3.7. Number of times a number is 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 -- 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.3.1. Programming -- 3.3.2. Generalization to expression in some base B -- 3.4. Words in which each letter is less than or equal to the position -- 3.4.1. Number of these words -- 3.4.2. Program -- 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.9.1. Exercise 1: words with different successive letters -- 3.9.2. Exercise 2: repeated purchases with a given sum of money -- 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.6.1. Three types of purchases each day with a sum of N dollars -- 5.6.2. Word building -- 5.7. Examples of languages -- 5.7.1. Language of parts of an element set {a, b, c, d, …} -- 5.7.2. Language of parts of a multi-set based on n elements a, b, c, etc., where these elements can be repeated as much as we want -- 5.7.3. Language of words made from arrangements taken from n distinct and non-repeated letters a, b, c, etc., where these words are shorter than or equal to n -- 5.7.4. Language of words based on an alphabet of n letters -- 5.8. The exponential generating function -- 5.8.1. Exercise 1: words based on three letters a, b and c, with the letter a at least twice -- 5.8.2. Exercise 2: sending n people to three countries, with at least one person per country -- 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 -- 6.6.1. Exercise 1: -- 6.6.2. Exercise 2: -- 6.6.3. Exercise 3: -- 6.6.4. Exercise 4: a geometrico-linguistic method -- 6.6.5. Exercise 5: paths of a given length that never intersect each other and where the four directions are allowed in the square grid -- Chapter 7. Arrangements and Combinations with Repetitions -- 7.1. Anagrams -- 7.2. Combinations with repetitions -- 7.2.1. Routes in a square grid -- 7.2.2. Distributing (indiscernible) circulars in personalized letter boxes -- 7.2.3. Choosing I objects out of N categories of object -- 7.2.4. Number of positive or nul integer solutions to the equation x0 + x1 + ...+ xn-1 = P -- 7.3. Exercises -- 7.3.1. Exercise 1: number of ways of choosing six objects out of three categories, with the corresponding prices -- 7.3.2. Exercise 2: word counting -- 7.3.3. Exercise 3: number of words of P characters based on an alphabet of N letters and subject to order constraints -- 7.3.4. Exercise 4: choice of objects out of several categories taking at least one object from each category -- 7.3.5. Exercise 5: choice of P objects out of N categories when the stock is limited -- 7.3.6. Exercise 6: generating functions associated with the number of integer solutions to an equation with n unknowns -- 7.3.7. Exercise 7: number of solutions to the equation x + y + z = k, where k is a given natural integer and 0 ≤ x ≤ y ≤ z -- 7.3.8. Exercise 8: other applications of the method using generating functions -- 7.3.9. Exercise 9: integer-sided triangles.

7.3.10. Revision exercise: sending postcards -- 7.4. Algorithms and programs -- 7.4.1. Anagram program -- 7.4.2. Combinations with repetition program -- Chapter 8. Sieve Formula -- 8.1. Sieve formula on sets -- 8.2. Sieve formula in combinatorics -- 8.3. Examples -- 8.3.1. Example 1: filling up boxes with objects, with at least one box remaining empty -- 8.3.2. Example 2: derangements -- 8.3.3. Example 3: formula giving the Euler number ϕ(n) -- 8.3.4. Example 4: houses to be painted -- 8.3.5. Example 5: multiletter words -- 8.3.6. Example 6: coloring the vertices of a graph -- 8.4. Exercises -- 8.4.1. Exercise 1: sending nine diplomats, 1, 2, 3, ..., 9, to three countries A, B, C -- 8.4.2. Exercise 2: painting a room -- 8.4.3. Exercise 3: rooks on a chessboard -- 8.5. Extension of sieve formula -- 8.5.1. Permutations that have k fixed points -- 8.5.2. Permutations with q disjoint cycles that are k long -- 8.5.3. Terminal nodes of trees with n numbered nodes -- 8.5.4. Revision exercise about a word: intelligent -- 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.6.1. Algorithm for obtaining the numbers of these left factors a(N, X) -- 9.6.2. Calculation following the lines of Catalan's triangle -- 9.6.3. Calculations based on the columns of the Catalan triangle -- 9.6.4. Average value of the height reached by left factors -- 9.6.5. Calculations based on the second bisector of the Catalan triangle -- 9.6.6. Average number of mountains for mountain ranges -- 9.7. Number of peaks of mountain ranges -- 9.8. The Catalan mountain range, its area and height.

9.8.1. Number of mountain ranges 2n long passing through a given point on the square grid -- 9.8.2. Sum of the elements of lines in triangle OO'B of mountain ranges 2n long -- 9.8.3. Sum of numbers in triangle OO'B -- 9.8.4. Average area of a mountain 2n long -- 9.8.5. Shape of the average mountain range -- 9.8.6. Height of the Catalan mountain range -- 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.2.1. Explicit formula v(n) -- 10.2.2. Return to u(n) number of mountain ranges based on three letters a, b, c and a link with v(n) -- 10.3. Example 1: domino tiling of an enlarged Aztec diamond -- 10.4. Example 2: domino tiling of half an Aztec diamond -- 10.4.1. Link between Schröder numbers and Catalan numbers -- 10.4.2. Link with Narayana numbers -- 10.4.3. Another way of programming three-line mountain ranges -- 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.2.1. Complementary exercise: rotation-type colorings of the vertices of a square -- 12.2.2. Example 2: pawns on a chessboard -- 12.2.3. Example 3: pearl necklaces -- 12.2.4. Example 4: coloring of a stick -- 12.3. Exercises.

12.3.1. Coloring the vertices of a square.