Combinatorial Analysis
- To have an understanding in combinations and permutations you must first have a basic understanding in probability.
- A probability is a numerical measure of the likelihood of the event. Probability is established on a scale from 0 to 1. A rare event has a probability close to 0; a very common event has a probability close to 1.
In order to solve and understand problems pertaining to probability you must know some vocabulary:
- An experiment, such as rolling a die or tossing a coin, is a set of trials designed to study a physical occurrence.
- An outcome is any result of a particular experiment. For example, the possible outcomes for flipping a coin are heads or tails.
- A sample space is a list of all the possible outcomes of an experiment.
- An event is a subset of the sample space. For example, getting heads is an event.
Counting Principles
- Theorem (The basic principle of counting): If the set E contains n elements and the set F contains m elements, there are nm ways in which we can choose, first, an element of E and then an element of F.
- Theorem (The generalized basic principle of counting): If r experiments that are to be performed are such that the first one may result in any of n1 possible outcomes, and if for each of these n1 possible outcomes there are n2 possible outcomes of the second experiment, and if for each of the possible outcomes of the first two experiments there are n3 possible outcomes of the third experiment, and if …, then there is a total of n1.n2…nr, possible outcomes of the r experiments.
- Theorem: A set with n elements has 2n subsets.
- Tree diagrams
Permutations
- Permutation: n!
- The number of permutations of n things taken r at a time:
- Theorem: The number of distinguishable permutations of n objects of k different types, where n1 are alike, n2 are alike, …, nk are alike and n=n1+n2+…+nk, is
Combinations
- Combination: The number of combinations of n things taken r at a time: (combinatorial coefficient; binomial coefficient)
- Binomial theorem:
- Multinomial expansion: In the expansion of (x1+x2+…+xk)n, the coefficient of the term , n1+n2+…+nk=n, is . Therefore,
Note that the sum is taken over all nonnegative integers n1, n2,…,nk such that n1+n2+…+nk=n.
The Number of Integer Solutions of Equations
- There are distinct positive integer-valued vectors (x1,x2,…,xy) satisfying x1+x2+…+xr = n, xi>0, i=1,2,…,r.
- There are distinct nonnegative integer-valued vectors (x1,x2,…,xy) satisfying x1+x2+…+xr = n.
Axioms of Probability
Sample Space and Events
- Experiment: An experiment (strictly speaking, a random experiment) is an operation which can result in two or more ways. The possible results of the experiment are known as outcomes of the experiment. These outcomes are known in advance. We cannot predict which of these possible outcomes will appear when the experiment is done.
- Sample Space: The set containing all the possible outcomes of an experiment as its element is known as sample space. It is usually denoted by S.
- Event: An event is a subset of the sample space S.
Illustration 1:
Let us consider the experiment of tossing a coin. This experiment has two possible outcomes: heads (H) or tails (T)
- sample space (S) = {H, T}
We can define one or more events based on this experiment. Let us define the two events A and B as:
A: heads appears
B: tails appears
It is easily seen that set A (corresponding to event A) contains outcomes that are favorable to event A and set B contains outcomes favorable to event B. Recalling that n (A) represents the number of elements in set A, we can observe that
n (A) = number of outcomes favorable to event A
n (B) = number of outcomes favorable to event B
n (S) = number of possible outcomes
Here, in this example, n (A) = 1, n (B) = 1, and n (S) = 2.
- Set theory concepts: set, element, roster method, rule method, subset, null set (empty set).
- Complement: The complement of an event A with respect to S is the subset of all elements of S that are not in A. We denote the complement of A by the symbol A’ (Ac).
- Intersection: The intersection of two events A and B, denoted by the symbol A∩B, is the event containing all elements that are common to A and B.
Two events A and B are mutually exclusive, or disjoint, if A∩B = φ that is, if A and B have no elements in common. - The union of the two events A and B, denoted by the symbol A∪B, is the event containing all the elements that belong to A or B or both.
Venn Diagram
- Sample space of an experiment: All possible outcomes (points)
- Events: subsets of the sample space
Impossible events (impossibility): Φ; sure events (certainty): S.
- DeMorgan’s laws:
Axioms of Probability
- Probability axioms:
(1) 0≤P(A)≤1;
(2) P(S)=1;
(3) P(A1∪A2∪…) = P(A1)+P(A2)+… If {A1, A2, …} is a sequence of mutually exclusive events. - Equally likely outcomes: the probabilities of the single-element events are all equal.
A number of sample events are said to be equally likely if there is no reason for one event to occur in preference to any other event.
Basic Theorems
- 0≤P(A)≤1;
- Complementary events:
- P(A∪B) = P(A) + P(B) – P(A∩B): inclusion-exclusion principle
- If A1, A2, An is a partition of sample space S, then
6. If a and a’ are complementary events, then P(A) + P(A’)=1.
Conditional Probability and Independence
Conditional Probability
- Conditional probability:
- Consider two events A and B defined on a sample space S. The probability of occurrence of event A given that event B has already occurred is known as the conditional probability of A relative to B.
P(A/B) = P(A given B) = probability of occurrence of A assuming that B has occurred
- It implies that the outcomes favorable to B become the possible outcomes and hence outcomes favorable to P(A/B) are outcomes common to A and B.
- Let n(B)=a and n(A∩B)=b. Suppose that the event B occurs.
- Then there are exactly a sample points and these points can be considered to be the sample space for the other event A.
- The event A in this sample space consists of b sample points common to A and B.
- Therefore, the probability of A in this sample space = b/a.
Thus the probability of A under the assumption that event B has occurred is:
and similarly
- The above result is known as conditional probability theorem.
2. If in an experiment the events A and B can both occur, then P(A∩B) = P(A)P(B|A) = P(B)P(A|B).
P(A∩B∩C) = P(A∩B)P(C|A∩B) = P(A)P(B|A)P(C|A∩B),
- The multiplication rule: P(A1∩A2 ∩…∩ An) = P(A1)P(A2|A1)P(A3|A1∩A2) … P(An|A1∩A2∩…∩An-1).
3. Partition: Let {B1, B2, …, Bn} be a set of nonempty subsets of the sample space S of an experiment. If the events B1, B2, …, Bn are mutually exclusive and B1∪B2∪…∪Bn = S, the set {B1, B2, …, Bn} is called a partition of S.
4. Theorem of total probability: If B1, B2, … is a partition of S, and A is any event, then
Total Probability Theorem: The probability that one of several mutually exclusive events A1, A2, .... An will happen is the sum of the probabilities of the separate events. i.e.
P(A1∪A2∪An) = P(A1)+P(A2)+.... + P(An)
5. Bayes’ Theorem: If B1, B2, … is a partition of S, and A is any event, then
Independence
- Independent events: If A, B are independent events ↔ P(A∩B) = P(A)P(B).
- Theorem: If A and B are independent, then are independent.
- The events A, B, and C are called independent if P(A∩B) = P(A)P(B), P(A∩C) = P(A)P(C), P(B∩C) = P(B)P(C), P(A∩B∩C) = P(A)P(B)P(C). If A, B, and C are independent events, we say that {A, B, C} is an independent set of events.
- The set of events {A1, A2, …, An} is called independent if for every subset of {A1, A2,…, An},
.
Important Results
Following results are easily derived from the definition of independent events.
- A and B are independent if
P(B/A) = P(B) and P(A/B) = P(A) - If A and B are independent, then P (A∩B) = P (A) P (B)
- A set of events A1, A2,... An are said to be pair-wise independent if
P(Ai n Aj) = P(Ai) P(Aj) ∀i ≠j. - The events A1, A2, ... An are mutually independent (or simply independent) if and only if the multiplication rule:
P(A1∩A2∩ .... Ak) = P(A1) P(A2) .... P(Ak) ... (1)
holds for every t triples of events, k = 2, 3, .... n. If (1) holds for k = 2 and may not hold for k = 3, 4, ....... n then events A1, A2, ... An are said to be pair wise independent. Thus mutually independent events are pair wise independent but converse is not true. - If A and B are mutually independent events such that P (A) ≠ 0 and P (B) ≠ 0, then the events A and B have at least one common sample point (i.e. they cannot be mutually exclusive). Or in general, mutually exclusive events are dependent events.
Question for Practice: Use the following information for Example
- A box contains 2 coins. One of them is a fair (F) coin and another one is a biased (UF) coin which always gives head as outcome when toss i.e. which has head on both sides. A coin is selected at random and it is tossed 'n' times. If all first 'n' outcomes results in a head,
- Then answer the following question using the convention (notations) given below:-
- The probability that (n+1)th toss also results in a head given as P(n+1,H)
- If first 'n' toss results in a head than the probability of selection of fair coin under above condition is denoted by P(n,F)
- If first 'n' toss results in a head than the probability of selection of unfair coin under above condition is represented by P(n,UF)
Example 1:
- If P(n,UF) = 128/129 then n is :-
A. 6 B. 7
C. 8 D. 9
Correct Answer: 2
Solution:
Event-1: section of coin
Event-2: tossing of the selected coin to ‘n’ times
P(n,F) – Is the probability of selection of fair coin if first n time head comes
So, using Baye’s theorem:
Let the symbol be as given below
P(n,H) = The prob. That (n+1)th outcome is also head
Example 2:
If P(n,H) = 33/34 then n is :-
A. 3 B. 4
C. 5 D. 6
Correct Answer: 2
Solution:
Example 3:
A. 2 B. 1/2
C. 1 D.
Correct Answer: 3
Solution:
Example 4:
- A biased coin has P probability for heads. It is tossed until tail appears for the first time. If the probability that no. of tosses required is even is 2/7 then P is
A. 4/7 B. 2/5
C. 3/5 D. 3/7
Correct Answer: 2
Solution:
Let X be the tosses required
P(X=r) = Pr-1(1-P)
E = Event of no of tosses to be even
P(E) = P[(X=2)U(X=4)------
= (1-P)P+P3(1-P)+P5(1-P)--------
= (1-P)P/(1-P2) = P/1+P
P/1+P = 2/7 P = 2/5 Hence (b)
*****
Next Subject - Probability Distribution
For a detailed schedule of GATE Civil Engineering(CE) 2019 Champion Study Plan, Click here
GATE Civil Engineering(CE) 2019 Champion Study Plan
To help you with your preparation for GATE 2019 Exam, BYJU'S Exam Prep has launched 2019 GATE Online Test Series based on the latest pattern and level of GATE exam with in-built virtual calculator.
Details about 2019 GATE Online Test Series
GATE 2019 Civil Engineering Syllabus, Download PDF!
Thanks
Team BYJU'S Exam Prep
Comments
write a comment