Discrete mathematics is the branch of mathematics dealing with objects having only discrete values. Firstly, it is the mathematics of natural numbers and secondly, classical problem statements are easy to understand even by non specialists.

Discrete mathematics is characterized by integers and deals with countable set and is an excellent tool for improving reasoning and problem-solving skills. Discrete mathematics are useful in studying computer algorithms, programming languages, cryptography, software development etc..

## History of Discrete Math

Discrete mathematics began at least as early as man learn to count. Counting principle is used to build a one to one correspondence between two entities and even today it is popular. Discrete objects combine with one another and there will be probabilities of various outcomes termed as combinations.

Using graph theory there were several attempts to prove the four color theorem and was successfully proved by Kenneth Appel and Wolfgang Haken in the year 1976. The topics that are considered to be a part of discrete mathematics include Information theory, Operation research, game theory, topology, discrete calculus and number theory.

## Discrete Math Relations

Relation is a set of ordered pairs. Consider two sets L and M, any subset of the cartesian product L $\times$ M is called a relation between L and M. Denoted as R: L $\rightarrow$ M
The set L is the domain and the set M is the codomain of the relation. If L = M then R will be in relation to L.

A relation on a set A is
 Reflexive If (a, a) $\in$ R, $\forall$ a $\in$ A Symmetric If (a, b) $\in$ R $\Rightarrow$ (b,a) $\in$ R             $\forall$ a,b $\in$ A Transitive If (a, b) $\in$ R and (b, c) $\in$ R $\Rightarrow$ (a,c) $\in$ R            $\forall$ a,b, c $\in$ A Anti symmetric If (a,b) $\in$ R and (b,a) $\in$ R             $\Rightarrow$ a = b,  $\forall$ a,b $\in$ A

## Discrete Math Functions

A function f from the set A to B is a relation from A to B if for each a $\in$ A, there exists a unique b $\in$ B with (a, b) $\in$ f.

where A is the domain and B is the co-domain of f respectively and is denoted as f: A  $\rightarrow$ B.

Let A and B be two non-empty sets then the function f: A  $\rightarrow$ B is

One-to-one function (Injective): Two elements of A should not be mapped to the same element of B.
i.e, For a, b $\in$ A and f(a), f(b) $\in$  B, a $\neq$ b  implies f(a)  $\neq$ f(b).

Onto function (Surjective): If for every b $\in$ B there exists a $\in$ A such that f(a) = b.

Bijective function:  If f is both one to one and onto.

## Discrete Math Applications

Applications of discrete mathematics is in:
1. Discrete convex analysis.
2. The vehicle routing problem
3. Distributed computing - a locality sensitive approach
4. Branching programs and
5. Optimization of Electoral systems.

## Discrete Math Graphs

In discrete mathematics we have different types of graph few of them are simple graph, multi graph, directed graph etc.

A simple graph is an undirected and unweighted graph having no graph loops or multiple edges. Also known as strict graph.

Multi graph or pseudo graph is a graph having multiple edges.  A multigraph holds undirected edges and there can be self loops. Nodes can be arbitrary.

The graphs which are connected with the set of nodes and with its edges are directed graph. A complete graph in which each edge is bidirected is the complete directed graph.

## Discrete Math Problems

### Solved Examples

Question 1: How many one to one functions will be there from a set of five elements to the sets containing the following numbers.
a) 4
b) 9
c) 8
d) 5
Solution:

In a, b, c there will be no elements as the number of elements should be same in each set.
d) 5! = 120, the number of permutations having 5 elements.

Question 2: How many permutations does the letters ABCDEFG contain
a) The string EAC ?
b) The string CEF and ABC?
Solution:

a) A set of strings is M = { F, G, B, D, EAC } As the permutations comes upto 5 elements it will be 5! = 120.
b) The string M will be M = { ABCEF, D, G} . Here C will appear only once and M has 3 set of strings so it is 3! = 6.