Essential Discrete Mathematics Formulas and Solved Examples
Mathematics is a subject that you’ll either love or dread. It is as simple as that. The people who dread Mathematics are the ones who have not witnessed the beauty of numbers and logic. So, remember it’s never too late for absorbing knowledge. This subject not only teaches us how to deal with problems but also instills common sense in us. Mathematics is one of the subjects which can never truly and entirely separate from our lives. The concepts of Mathematics serve as the basis of various other subjects like physics, computer science, architecture etc. Mathematics is divided into 4 branches namely, arithmetic, algebra, geometry, and trigonometry. Did you know that Archimedes is considered as the Father of Mathematics? Today we’ll learn about Discrete Mathematics.
Do you know what Discrete Mathematics is? Do you know about Discrete Mathematics and its applications? We’ll discuss it all here.
Discrete Mathematics
Discrete Mathematics is about Mathematical structures. It is about things that can have distinct discrete values. Discrete Mathematical structures are also known as Decision Mathematics or Finite Mathematics. This is very popularly used in computer science for developing programming languages, software development, cryptography, algorithms, etc.
(Image will be uploaded soon)
Discrete Mathematics Problems and Solutions
Now let’s quickly discuss and solve a Discrete Mathematics problem and solution:
Example 1:
Determine in how many ways can three gifts be shared among 4 boys in the following conditions-
i) No one gets more than one gift.
ii) A boy can get any number of gifts.
Solution:
i) The first gift can be given in 4 ways as one cannot get more than one gift, the remaining two gifts can be given in 3 and 2 ways respectively.
The total number of ways = 4 x 3 x 2 = 24.
ii) As there is no restriction, each gift can be given in 4 ways.
The total number of ways = 43 = 64.
Discrete Mathematics Topics
Various concepts of Mathematics are covered by Discrete Mathematics like:
Set Theory
Permutation and Combination
Graph Theory
Logic
Sequence and Series
Set Theory
Set Theory is a branch of Mathematics that deals with collection of objects. It starts with the fundamental binary relation between an object M and set A.
Imagine there are two sets, say, set A and set B. Set A has numbers 1-5 and Set B has numbers 1-10. You can see that all the elements of set A are in set B. This makes set A a subset of set B.
A={1,2,3,4,5} B={1,2,3,4,5,6,7,8,9,10}
Imagine there are two sets, say, set A and set B. Set A has numbers 1-5 and Set B has numbers 1-10. If we combine the elements of set A and set B, then the set we get is called a union set. So, we get the union of set A and set B.
(AUB)={1,2,3,4,5,6,7,8,9,10}
Imagine there are two sets, say, set A and set B. Set A has numbers 1-5 and Set B has numbers 1-10. If we take the elements that are present in both sets then we get the intersection.
(A∩B)={1,2,3,4,5}
Imagine there are two sets, say, set A and set B. Set A has numbers 1-5 and Set B has numbers 1-10. When we are trying to find the Cartesian Product of set A and B, we are actually making an ordered pair. (AXB)={(1,1);(1,2).........(5,4);(5,5)}
Remember (AXB)≠(BXA)
Permutation and Combination
Permutation and Combination are all about counting and arranging from the given data. The permutation is all about arranging the given elements in a sequence or order. The combination is about selecting elements in any way required and is not related to arrangement.
You can use the formula for permutation – nPr = \[\frac{(n!)}{(n-r)!}\]
Where r objects have to be arranged out of a total of n number of objects
The formula for combination is— \[nCr=\frac{n!}{r!(n-r)!}\]
Where r objects have to be chosen out of a total of n number of objects
Logic
Logic can be defined as the study of valid reasoning. The logical formulas are discrete structures and so are proofs thus, forming finite trees. The truth values of logical formulas form a finite set. They are restricted to only two values either true or false.
Graph Theory
Graph Theory is about the study of graphs. They are discrete Mathematical structures and are used to model in relation to pairs between the objects. The graph we are discussing here consists of vertices which are joined by edges or lines. Graphs are one of the most important objects of study in Discrete Mathematics. Discrete Mathematics and graph theory are complementary to each other. Graphs are present everywhere. They are models of structures either made by man or nature. They can model various types of relations and process dynamics in physical, biological and social systems. They can also display networks of communication, data organization, the flow of computation, etc. they are also used in geometry and in topology.
Sequence and Series
A sequence is a set of numbers which are arranged in a definite order and following some definite rule. A series is a sum of terms which are in a sequence.
Formulas Related to Some Special Series
The sum of 1st n natural numbers:
\[S_{n} = \frac{n(n+1)}{2}\]
The sum of the squares of 1st n natural numbers:
\[S_{n} = \frac{n(n+1)(2n+1)}{6}\]
The sum of the cubes of first n natural numbers:
\[S_{n} = \text{(Sum of the first n natural numbers)}2\]
\[= \frac{n(n+1)}{22}\]
Fun Facts
On contrary to real numbers that differs "seamlessly", Discrete Mathematics studies objects such as graphs, integers and statements in reasoning
The objects studied in Discrete Mathematics do not differ seamlessly, in fact, have varied, Discrete Mathematics does not include matters in "continuous mathematics" such as algebra and calculus
Continuous and Discrete Mathematics
Mathematics can be divided into two categories: continuous and discrete.
Continuous Mathematics is based on a continuous number line or real numbers in continuous form. It is defined by the fact that there is virtually always an endless quantity of numbers between any two integers. In continuous Mathematics, for example, a function can be depicted as a smooth curve with no breaks.
Discrete Mathematics involves separate values; that is, there are a countable number of points between any two points in Discrete Mathematics. If we have a finite number of items, for example, the function can be defined as a list of ordered pairs containing those objects and displayed as a complete list of those pairs.
Use of Discrete Mathematics in Real World
It is commonly stated that Mathematics may be used to solve a wide range of practical problems. Cathy and MathILy-Er focus on Discrete Mathematics, which supports nearly half of pure Mathematics, operations research, and computer science in general. Discrete Mathematics is becoming more prevalent in academia and industry as time goes on. But what exactly are the applications that people are referring to when they claim Discrete Mathematics can be used? What issues are being addressed? This article attempts to answer those questions. There are summaries of Discrete Mathematics applications in our daily lives, as well as in major and interesting research and corporate applications, with links to extended explanations.
Vedantu: A Mentor
In case you're a student who is preparing for an exam, you can refer to the many sorts of courses available on Vedantu's website or app. These courses will help you in many ways like, you will learn how to write both long and short solutions in various sorts of tests. Vedantu's website also provides you with various study materials for exams of all CBSE Classes like 9th, 10th, 11th, 12th, and other sorts of board and state-level examinations. On Vedantu, you will also learn about the pattern of past year question papers as these papers are eventually going to help you study thoroughly for your future examinations.
If as a student, you are interested in learning more about Vedantu and want a friend that would help you to score well in exams, you can visit the Vedantu website. It is a portal through which you can access all of the essential study resources and it can also be dubbed as an educational tool crafted by a large number of dedicated instructors who put their expertise and hard work into making these resources. So, just visit the website and check out the different types of materials available there.
FAQs on Discrete Mathematics Explained for Students
1. What is Discrete Mathematics?
Discrete Mathematics is the branch of mathematics that studies mathematical structures that are fundamentally discrete rather than continuous. This means it deals with countable, distinct, and separate values. Instead of concepts on a smooth, unbroken number line, it focuses on individual points like integers, the steps in a computer algorithm, or logical statements that can only be true or false.
2. How does Discrete Mathematics differ from Continuous Mathematics like Algebra or Calculus?
The fundamental difference lies in the nature of the values they study. Discrete Mathematics focuses on finite or countably infinite sets of objects. In contrast, Continuous Mathematics deals with data that can take any value within a given range, like temperature or height. A simple way to think about it is that discrete math counts things (e.g., number of students), while continuous math measures things (e.g., the exact height of a student).
3. What are the key topics covered under the umbrella of Discrete Mathematics?
Discrete Mathematics is a broad field with several important branches that form the basis for logic and computer science. The primary topics include:
- Set Theory: The study of collections of objects and their properties.
- Graph Theory: The study of networks made of points (vertices) and the lines connecting them (edges).
- Logic: The study of the principles of valid reasoning and formal proof.
- Combinatorics: The art of counting, which includes permutations and combinations.
- Number Theory: The study of integers and their unique properties.
4. Can you provide a simple, real-world example of a problem solved using Discrete Mathematics?
A classic example is planning a delivery route. A GPS uses principles from graph theory to find the shortest or fastest path between multiple points. The map is modelled as a graph where intersections are vertices and roads are edges with assigned weights (like distance or travel time). The GPS algorithm calculates the most efficient path, which is a discrete problem involving a finite number of points and connections.
5. Why is Discrete Mathematics considered a foundational subject for Computer Science?
Its importance for Computer Science is immense because modern computers operate on discrete data—specifically, bits that are either 0 or 1. Key applications include:
- Algorithms: Designing and analysing the efficiency of computer procedures.
- Databases: Using set theory and relational algebra to manage and query data.
- Cryptography: Applying number theory to create secure codes and protect information.
- Networking: Using graph theory to model and optimise the flow of data across the internet.
- Software Development: Employing formal logic to verify that software is correct and free of bugs.
6. What is the core difference between permutations and combinations in this field?
Both permutations and combinations are fundamental counting principles in Discrete Mathematics, but they differ on one key factor: order.
- Permutations are arrangements where the order of selection is important. For example, choosing a president, vice-president, and treasurer is a permutation because the assigned roles matter.
- Combinations are selections where the order does not matter. For example, choosing a committee of three people is a combination because the final group is the same regardless of the order in which individuals were picked.
7. How does graph theory, a part of Discrete Mathematics, help model real-world networks?
Graph theory provides a powerful and versatile framework for modelling complex relationships. In a graph, objects are represented by vertices (nodes) and their connections by edges (lines). For example:
- In social media: Each user profile is a vertex, and a 'friend' or 'follow' connection is an edge. This model helps analyse influence, find communities, and track the spread of information.
- In logistics: Cities are vertices, and flight or road routes are edges. This helps companies solve optimisation problems like finding the most efficient delivery routes.
