Introductory Discrete Mathematics

V. K . Balakrishnan

• Publisher: Dover Publications
• Year: 2012
• ISBN:
  9780486140384
• Topic: Matemáticas
• Subtopic: Matemáticas discretas

This concise text offers an introduction to discrete mathematics for undergraduate students in computer science and mathematics. Mathematics educators consider it vital that their students be exposed to a course in discrete methods that introduces them to combinatorial mathematics and to algebraic and logical structures focusing on the interplay between computer science and mathematics. The present volume emphasizes combinatorics, graph theory with applications to some stand network optimization problems, and algorithms to solve these problems.
Chapters 0–3 cover fundamental operations involving sets and the principle of mathematical induction, and standard combinatorial topics: basic counting principles, permutations, combinations, the inclusion-exclusion principle, generating functions, recurrence relations, and an introduction to the analysis of algorithms. Applications are emphasized wherever possible and more than 200 exercises at the ends of these chapters help students test their grasp of the material.
Chapters 4 and 5 survey graphs and digraphs, including their connectedness properties, applications of graph coloring, and more, with stress on applications to coding and other related problems. Two important problems in network optimization ― the minimal spanning tree problem and the shortest distance problem ― are covered in the last two chapters. A very brief nontechnical exposition of the theory of computational complexity and NP-completeness is outlined in the appendix.

Combinatorics

1.1 TWO BASIC COUNTING RULES

Combinatorics is one of the fastest-growing areas of modern mathematics. It has many applications to several areas of mathematics and is concerned primarily with the study of finite or discrete sets (much as the set of integers) and various structures on these sets, such as arrangements, combinations, assignments, and configurations. Broadly speaking, three kinds of problems arise while studying these sets and structures on them: (1) the existence problem, (2) the counting problem, and (3) the optimization problem. The existence problem is concerned with the following question: Does there exist at least one arrangement of a given kind? The counting problem, on the other hand, seeks to find the number of possible arrangements or configurations of a certain pattern. The problem of finding the most efficient arrangement of a given pattern is the optimization problem. In this chapter we study techniques for solving problems that involve counting. These techniques form a basis for the study of enumerative combinatorics, which is really the theory of counting where results involving counting are obtained without carrying out the exact counting process, which could be tedious.

Suppose that there are 10 mathematics majors and 15 computer science majors in a class of 25 and we are required to choose a student from the class to represent mathematics and another student to represent computer science. Now there are 10 ways of choosing a mathematics major and 15 ways of choosing a computer science major from the class. Furthermore, the act of choosing a student from one area in no way depends on the act of choosing a student from the other. So it is intuitively obvious that there are 10 × 15 = 150 ways of selecting a representative from mathematics and a representative from computer science. On the other hand, if we are required to select one representative from mathematics or from computer science, we have only 10 + 15 = 25 ways of accomplishing this. In the former case we used the multiplication rule of counting and in the latter the addition rule. These two rules can be stated formally as follows.

MULTIPLICATION RULE (The Rule of Sequential Counting)

Suppose that there is a sequence of r events E₁, E₂, . . . , E_r such that (1) there are n_i ways in which E_i(i = 1, 2, . . . , r) can occur, and (2) the number of ways an event in the sequence can occur does not depend on how the events in the sequence prior to that event occurred. Then there are (n₁) · (n₂) · . . . · (n_r) ways in which all the events in the sequence can occur.

ADDITION RULE (The Rule of Disjunctive Counting)

Suppose that there are r events E₁, E₂, . . . , E_r such that (1) there are n_i outcomes for E_i(i = 1, 2, . . . , r), and (2) no two events can occur simultaneously. Then there are (n₁) + (n₂) + · · · + (n_r) ways in which one of these r events can take place.

These two elementary rules are very useful in solving counting problems without carrying out explicit enumeration. However, if one is not careful, they are likely to be misused, producing erroneous results, as may be seen from some of the examples we discuss in what follows.

Example 1.1.1

There are five characters—two letters of the alphabet followed by three digits—which appear on the back of one series of a microcomputer made by an electronics company. The number of possible computers manufactured in this series is (1) 26 × 26 × 10 × 10 × 10 = 676,000 if characters can repeat, (2) 26 × 25 × 10 × 10 × 10 = 650,000 if letters cannot repeat, and (3) 26 × 25 × 10 × 9 × 8 = 468,000 if no characters can repeat. We use the multiplication rule here.

Example 1.1.2

A professor has 25 students in her advanced calculus course and 31 students in her statistics course. Thirteen students have signed up for both the courses. There are three events here, no two of which can occur simultaneously: (1) The event that a student chosen at...