Discrete Mathematics

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Introduction

Discrete Mathematics is a branch of mathematics that is concerned with “discrete” mathematical structures. It provides an essential foundation for virtually every area of computer science and its applications are vast. It is increasingly being applied in the practical fields of mathematics and computer science. Discrete mathematics is in contrast to continuous mathematics, which deals with structures which can range in value over the real numbers, or have some non-separable quality. Discrete Mathematics concerns itself mainly with finite collections of discrete objects. With the growth of digital devices, especially computers, discrete mathematics has become more and more important. Discrete mathematics is the mathematical language of computer science, and as such, its importance has increased dramatically in recent decades.

Topics covered in discrete mathematics related to computer science:

• Combinatorics

Combinatorics is often concerned with how things are arranged. In this context, an arrangement is a way objects could be grouped. The most basic rules regarding arrangements are the rule of product and the rule of sum.

Sum Rule Principle

Assume some event E can occur in m ways and a second event F can occur in n ways, and suppose both events cannot occur simultaneously. Then E or F can occur in m + n ways. In general, if there are n events and no two events occurs in same time then the event can occur in n1+n2..........n ways.

Product Rule Principle

Suppose there is an event E which can occur in m ways and, independent of this event, there is a second event F which can occur in n ways. Then combinations of E and F can occur in mn ways. In general, if there are n events occurring independently then all events can occur in the order indicated as n1 x n2 x n3.........n ways.

Permutation

A permutation is an arrangement of some elements in which order matters. Any arrangement of a set of n objects in a given order is called Permutation of Object. Any arrangement of any r ≤ n of these objects in a given order is called an r-permutation or a permutation of n object taken r at a time. It is denoted by P (n, r)  $_{n}P_{r}={\frac {n!}{(n-r)!}}$

Combination

A combination is an arrangement of objects without regard to order. The number of all combinations of n things, taken r at a time is C (n, r)  $_{n}C_{r}={\frac {n!}{r!(n-r)!}}$

• Set Theory

A Set is an unordered collection of objects, known as elements or members of the set. An element ‘a’ belong to a set A can be written as ‘a ∈ A’, ‘a ∉ A’ denotes that a is not an element of the set A. German mathematician G. Cantor introduced the concept of sets. He had defined a set as a collection of definite and distinguishable objects selected by the means of certain rules or description. Sets can be represented mainly in two ways −

Roster or tabular form:

In this form of representation we list all the elements of the set within braces { } and separate them by commas. If A= set of all even numbers less then 10 then in the roster from it can be expressed as A={ 2,4,6,8}.

Set Builder Notation:

The set is defined by specifying a property that elements of the set have in common. The set is described as A={x:p(x)}In Set-builder set is described by a property that its member must satisfy. {x : x is natural number less than 10}.

Equal Set:

Two sets are said to be equal if both have same elements. For example, A = {2, 4, 6, 8} and B = {4, 2, 6, 8} are equal sets. Order of elements of a set doesn’t matter.

Cardinality:

The total number of unique elements in the set is called the cardinality of the set. Cardinality can also be extended to infinite sets. Although this kind of cardinality cannot be counted, each cardinality can be compared with another cardinality.

• Graph Theory
• Mathematical Induction
• Boolean Algebra
• Probability Theory