Published: Mar Downloads: 96 Pages: Published: Jul Downloads: Pages: Mathematics: Ages 5 to 6 Glen K. Published: May Downloads: Pages: Published: Mar Downloads: Pages: Published: Apr Downloads: Pages: Calculating Advanced Statistics John R. Arithmetic for Engineers Charles B. Published: Jan Downloads: Pages: If we consider two tasks A and B which are disjoint i. From his home X he has to first reach Y and then Y to Z.
He may go X to Y by either 3 bus routes or 2 train routes. From there, he can either choose 4 bus routes or 5 train routes to reach Z. How many ways are there to go from X to Z? Permutations A permutation is an arrangement of some elements in which order matters. In other words a Permutation is an ordered Combination of elements. Different three digit numbers will be formed when we arrange the digits. There are n number of ways to fill up the first place.
After filling the first place n -1 number of elements is left. Hence, there are n-1 ways to fill up the second place. After filling the first and second place, n-2 number of elements is left. Hence, there are n-2 ways to fill up the third place. The number of permutations of n dissimilar elements when r specified things always come together is: r! The number of permutations of n dissimilar elements when r specified things never come together is: n! Solution The cardinality of the set is 6 and we have to choose 3 elements from the set.
Here, the ordering does not matter. Problem 2 There are 6 men and 5 women in a room. In how many ways we can choose 3 men and 2 women from the room? Now, it is known as the pigeonhole principle.
Pigeonhole Principle states that if there are fewer pigeon holes than total number of pigeons and each pigeon is put in a pigeon hole, then there must be at least one pigeon hole with more than one pigeon.
Ten men are in a room and they are taking part in handshakes. There must be at least two people in a big city with the same number of hairs on their heads. The Inclusion-Exclusion principle The Inclusion-exclusion principle computes the cardinal number of the union of multiple non-disjoint sets. How many like both coffee and tea? Solution Let X be the set of students who like cold drinks and Y be the set of people who like hot drinks. We often try to guess the results of games of chance, like card games, slot machines, and lotteries; i.
Probability can be conceptualized as finding the chance of occurrence of an event. Mathematically, it is the study of random processes and their outcomes. The laws of probability have a wide applicability in a variety of fields like genetics, weather forecasting, opinion polls, stock markets etc.
Basic Concepts Probability theory was invented in the 17th century by two French mathematicians, Blaise Pascal and Pierre de Fermat , who were dealing with mathematical problems regarding of chance. Before proceeding to details of probability, let us get the concept of some definitions. Random Experiment: An experiment in which all possible outcomes are known and the exact output cannot be predic ted in advance is called a random experiment.
Tossing a fair coin is an example of random experiment. Sample Space: When we perform an experiment, then the set S of all possible outcomes is called the sample space.
After tossing a coin, getting Head on the top is an event. The word "probability" means the chance of occurrence of a particular event. The best we can say is how likely they are to happen, using the idea of probability. Steps to find the probability: Step 1: Calculate all possible outcomes of the experiment. Step 2: Calculate the number of favorable outcomes of the experiment.
Step 3: Apply the corresponding probability formula. The probability of an event always varies from 0 to 1. For an impossible event the probability is 0 and for a certain event the probabilit y is 1. If the occurrence of one event is not influenced by another event, they are called mutually exc lusive or disjoint. If A1 , A P An Properties of Probability 1. If an event A is a subset of another event B i.
This is written as P B A. If event A and B are mutually exclusive, then the conditional probability of event B after the event A will be the probability of event B that is P B. What is the probability that a teenager owns bike given that the teenager owns a cycle? Solution Let us assume A is the event of teenagers owning only a cycle and B is the event of teenagers owning only a bike. What is the probability that a student plays volleyball given that the student plays cricket?
Solution Let us assume A is the event of students playing only cricket and B is the event of students playing only volleyball. To find the defective laptops all of them are tested one-by-one at random.
What is the probability to find both of the defective laptops in the first two pick? Solution Let A be the event that we find a defective laptop in the first test and B be the event that we find a defective laptop in the second test.
Problem Consider three pen-stands. The first pen-stand contains 2 red pens and 3 blue pens; the second one has 3 red pens and 2 blue pens; and the third one has 4 red pens and 1 blue pen.
There is equal probability of each pen-stand to be selected. If one pen is drawn at random, what is the probability that it is a red pen?
Solution Let Ai be the event that ith pen-stand is selected. This part illustrates the method through a variety of examples. Definition Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number. The technique involves two steps to prove a statement, as stated below: Step 1 Base step : It proves that a statement is true for the initial value.
How to Do It Step 1: Consider an initial value for which the statement is true. So, it is proved that 3n — 1 is a multiple of 2. Strong Induction Strong Induction is another form of mathematical induction. The procedure for finding the terms of a sequence in a recursive manner is called recurrence relation.
We study the theory of linear recurrence relations and their solutions. Finally, we introduce generating functions for solving recurrence relations. So, this is in the form of case 3. First part is the solution a h of the associated homogeneous recurrence relation and the second part is the particular solution a t. For example, the number of ways to make change for a Rs. In this part, we will study the discrete structures that form the basis of formulat ing many a real-life problem.
The two discrete structures that we will cover are graphs and trees. A graph is a set of points, called nodes or vertices, which are interconnected by a set of lines called e dges. The study of graphs, or graph theory is an important part of a number of disciplines in the fields of mathematics, engineering and computer science. What is a Graph? Degree of a Vertex: The degree of a vertex V of a graph G denoted by deg V is the number of edges incident with the vertex V. For the above graph the degree of the graph is 3.
The Handshaking Lemma: In a graph, the sum of all the degrees of vertices is equal to twice the number of edges. Null Graph A null graph has no edges. If a graph G is unconnected, then every maximal connected subgraph of G is called a connected component of the graph G.
In a regular graph G of degree r, the degree of each vertex of G is r. The complete graph with n vertices is denoted by Kn a c b Complete graph K3 Cycle Graph If a graph consists of a single cycle, it is called cycle graph.
A graph G is bipartite if and only if all closed walks in G are of even length or all cycles in G are of even length. The complete bipartite graph is denoted by Kr,s where the graph G contains x vertices in the first set and y vertices in the second set. An entry A[V x ] represents the linked list of vertices adjacent to the Vx-th vertex. The adjacency list of the graph is as shown in the figure below: a b c b a c c a b d d c Planar vs.
Non-planar graph Planar graph: A graph G is called a planar graph if it can be drawn in a plane without any edges crossed. If we draw graph in the plane without edge crossing, it is called embedding the graph in the plane.
It is easier to check non-isomorphism than isomorphism. It maps adjacent vertices of graph G to the adjacent vertices of the graph H. A homomorphism is an isomorphism if it is a bijective mapping. Homomorphism always preserves edges and connectedness of a graph. The compositions of homomorphisms are also homomorphisms. To find out if there exists any homomorphic graph of another graph is a NP-complete problem.
Euler Graphs A connected graph G is called an Euler graph, if there is a closed trail which includes every edge of the graph G. An Euler path is a path that uses every edge of a graph exactly once. An Euler path starts and ends at different vertices. An Euler circuit is a circuit that uses every edge of a graph exactly once.
An Euler circuit always starts and ends at the same vertex. A connected graph G is an Euler graph if and only if all vertices of G are of even degree, and a connected graph G is Eulerian if and only if its edge set can be decomposed into cycles.
Hamiltonian walk in graph G is a walk that passes through each vertex exactly once. This is called Dirac's Theorem. This is called Ore's theorem. The objective is to minimize the number of colors while coloring a graph. The smallest number of colors required to color a graph G is called its chromatic number of that graph. Graph coloring problem is a NP Complete problem.
Method to Color a Graph The steps required to color a graph G with n number of vertices are as follows: Step 1. Arrange the vertices of the graph in some order. Step 2. Choose the first vertex and color it with the first color. Step 3. Choose the next vertex and color it with the lowest numbered color that has not been colored on any vertices adjacent to it. If all the adjacent vertices are colored with this color, assign a new color to it.
Repeat this step until all the vertices are colored. Follow us on FB — Smartzworld. A1: Study of countable, otherwise distinct and separable mathematical structures are called as Discrete mathematics. It focuses mainly on finite collection of discrete objects. The field has become more and more in demand since computers like digital devices have grown rapidly in current situation.
A2: Combinatorics is the mathematics of arranging and counting. The field also concerned with the way things are arranged which includes rule of sum and rule of product. Permutation and combination come under this topic.
A3: Permutation is an arrangements of things with regards to order where as combination is an arrangement of things without regard to order.
A4: A branch of mathematics concerned with collections of object is called Set theory. The sets could be discrete or continuous which is concerned with the way sets are arranged, counted or combined. The way sets can be combined are described by Intersection and Union. Average rating 4.
0コメント