Combinatorics - Counting Problems

Bijection Approach

Bijection is one of the approach used in combinatorics Bijection is transforming some new problem to known problem set. Bijection with another problem set reduces new problem to similar known problem.

Bijection with [Bit]strings

Problem Move from cordinate (0,0) to (3,4) with only a move in either x or y at a time

Bijection with the string with 3X and 4Y where X is move in X direction and Y is move in Y direction
like XXXYYYY
possible arrangements with 3X and 4Y

C(7 3)

Problem 5 objects to be placed in 3 boxes
Bijection to string with 2X where X divides the string like 2X in string will divide string in 3parts or 3boxes

********X***********X******
box1              box2                 box3

and 5Y where Y represents object to be placed
like XXXXXYY
Total arrangements C(7 2)

Problem 15 books are on shelf in how many ways to choose 5 books so that no two chosen book is adjacent

Bijection with bit string with 5 1's and 6 0's where 0 is for selected book and 1 for not selected book

lets take some instances for selecting books
101010101000
1000010010001001
00101001010001

now question states that there must be atleast one not selected book (0) between each selected book (1)

so the required base patten is
101010101
or more appropiately
10⁺10⁺10⁺10⁺
that is there should be at least one 0 between two 1's

Now remaining books are 15 - 9 = 6

there can be others books before between and after this pattern like

101010101 000000 after this pattern
000000101010101 before this pattern
1000010010001001 between this pattern

if we consider 10 to be one element now we have elements as

(10) (10) (10) (10) (1) 0 0 0 0 0 0

so its arrangement of this elements which is (11 6)

Problem  Number of subsets of set with n elements
Bijection n length bit string where  0 is for element not selected and 1 for element selected
so for set {x1,x2,x3....xn}
if we consider subset {x2,x5} we will have bit string 0100100..0 where 2nd and fifth are 1 rest zero
so if we count number bit strings with zero and 1 we would have the possible subsets
Number of subsets is 2^n as each position can be either zero or one


Placing n indistinguishable objects in k distinguishable boxes in general
Like we saw number of ways to put 3 objects in to 2 boxes

box1       box2

aaa

                  aaa

aa                a

a                 aa




This problem was mapped into problem of positioning 1 in the four bitstring where the left of 1 specify the number of objects in box1 and right of 1 specify number of object in box2
or we need one divider for making two boxes
**********|***********
box1                   box2
like 0001 divides object, all in box1 none in box2

that is if we have to place indistinguishable objects in k boxes then we would need k-1 dividers
so general formula for placing n indistinguishable objects in k distinguishable boxes is
(n+(k-1))C(k-1)


Each box contains at least one object
If the constraint is such that each box should contain atleast 1 object or box can not be empty

we first place one object in each box which can be done in 1 way since objects are indistinguishable and then distribute remaining n-k objects in k boxes which is (n-k)c(k-1)

or if we look at bitstring when there are three boxes 5 objects and atleast one objet should be there in each

we can assume following to be single object and find the possible combinations

(01) (010) 0 0

or its pattern

(0)+1(0)+1(0)+



Problem A doughnut shop offers Plain, Glazed, Hoclate and Jelly doughnuts How many different orders of dozen doughnuts are possible. Also find when we need to select atleast one from each variety

Of the dozen doughnuts the various possibilities are

we select 2P 3G 4H 3J or 7P 3G 0H 2J and so

we need to place 12 indistinguishable doughnuts in to 4 distinguishable boxes which is (12+(4-1))C(4-1) = 15C3

or if we map the problem to bit string it is like

(0)*1(0)*1(0)*1(0)*

zero's specify doughnut in that group consider simple instance like

000001000010010


At least one from all :
when we need to select atleast one from each variety its like selecting 4 doughnuts from each variety first which can be done in single way and then selecting 8 doughnuts

which is (8+4-1)C(4-1)


Problem. Consider number from 1 to 20 we need to select three numbers from this group then what is probabability of  getting pair of consecutive numbers in the three selected numbers.

Sample space S is  = (20 3) that is ways to select three numbers
the selected numbers could be like
1 2  5, 2 5 6,
so a consecutive pairs can be selected in 19 ways 12,23,34,45,... 1920
and then select any number this can be done in 18 ways (except two selected numbers)
giving E = 19*18 but
there are possibility when we select the consecutive number like 4 5 and we select other number as say 6 these selection will repeat when we select consecutive number 5 6 and select other number as 4
so this repeated selections will be when we select three consecutive numbers
so number of consecutive numbers is = 18
actual E= 19*18 -18
probability = E/S

Problem In how many ways can 2n students be paired up
Arrange students in row and first each two 12 34 ..
consider 4 students 1 2 3 4 now we first find the way to arrange them
4!
1234

1243
2143
2134
1324
1342
3124
3142
1423
1432
4132
4123
2341
2314
3214
3241
2431
2413
4231
4213
3412
3421
4321
4312

 we are overcounting here by
(number of ways of arranging first ) (number of ways of arranging second pair)
(2!)(2!)
now we are left with
//pending

Problem How many different outcomes are possible when 3 similar dice are tossed
Solution
If we had three distinct dice that is if we consider dice as numbered A B and C
then number of different outcomes are 6^3 that is we differentiate between outcomes
3 4 3 and
3 3 4

Here for similar dice number of different outcomes means that if on two dice its n1 and on third its n2
we donot differentiate between two dice which has n1 output so cases like
1 1 2
2 1 1
1 2 1 are all same
we can think of possible outputs as box numbered 1 2 3 4 5 6
then output of dice toss would be like

**       |         *        |              |            |           |

that is we got number 1 on two dice and number 2 on one here for six containers we have five separator
***|||||
so number of arrangements of  * and | that is C(8 3)

Number of partitions of set of n objects into k groups

Stirling number of second kind

S(n,0) = 0
S(n,1) =S(n,n) = 1

Triangular Property
S(n,k) = S(n-1,k-1)+k*S(n-1,k)
can be interpreted as partition of n objects into k groups would either contain subset {n} or it does not
If it contains the subset {n} then we have one group and remaining groups can be formed in S(n-1,k-1)
If it is not contained then we have n-1 objects which should be partitioned into k groups S(n-1,k)

that each number can be derived from number directly above it and before that.
for k between 0 to n
                0    1     2     3     4         ------->k size of partition
----------------------------
S(3,k) =  0    1     3      1
S(4,k) =  0    1     7      6     1

Sum {k=0 to n }(S(n,k))
that is partition of all size is done by bell number

Counting Functions

Consider set A of r elements and set B of n elements

Counting number of functions
each value from set A can be assinged any value from the set B

for each value there are n options so its n^r

Counting Injective functions
Injective function one-to-one function  states that  no two values from set A can be assigned same value from set B. So if we have

r>N we don't have sufficient values in the set B and from pigeonhole principle we can prove that atleast two values  will have same mappings so its 0

for r

Counting Bijections

Bijection states that every value in y should have their image in x + injection property

so for
r != n its 0 and for
r = n its n!


Counting Surjective functions

sujection or onto states that image of function is equal to its Range that is all the y in image are mapped to some x in domain

If r elements in the domain and n elements in the  image

we first partition r elements in the domain to map to all n elements in the image

1)partition the elements in set X, call it S(r,n), in to n partitions

if we partition above function where r=3 and n=2  we would have partitions like {12,3} {13,2} {23,1}

2) we pick value for each partition that is for (12) and for (3) we can pick value for them in n! ways

So we have number of onto functions = S(r,n)*n!
where S(r,n) is Stirling number


Another method for counting surjection

Let m be number of element in domain and n be number of element in co-domain
Using principle of inclusion and exclusion
let elements y1 y2 ..yn be not in range and conidtion p1 p2 ....pn represent this resp.
then for surjection there should be all element in codomain should be in range so

N(p1'p2'..pn') = N- N(p1p2p3)

that is condition when all elements not mapped = total number of function - condition when all the element are mapped

N= n^m

N(p1p2p3) = when 1 element is not mapped + when 2 elements are not mapped +.. when all m elements are not mapped

N(p1p2p3) = C(n,1)(n-1)^m +C(n,2) (n-2)^m.........(-1)^n-1 C(n,n-1) 1^m

so total surjections are
n^m -C(n,1)(n-1)^m +C(n,2) (n-2)^m.........(-1)^n-1 C(n,n-1) 1^m


Problems number of way to assign 5 different jobs to 4 different employee such that every employee gets at least one job

Solution
Its surjection from 5 to 4 elements n=4 and m=5

4^5 - c(4,1)3^5 + c(4,2) 2^5 - c(4,3)

References
Some useful links for combinatorics problems and solutions

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2005/assignments
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-sma-5512-fall-2002/assignments/ http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/
http://www.geometer.org/mathcircles/solnscount.pdf
www.cs.pitt.edu/~adamlee/courses/fall_08/cs441/.../lecture21.pdf
http://2000clicks.com/MathHelp/CountingObjectsInBoxes.aspx
http://www.math.cornell.edu/~web4410/       //solutions to 'A course in combinatorics '

Relation and Functions

Function
f(A) --> B
each element of A is mapped to exactly one element in B
A is domain and B is codomain, or B is image and A is pre image of B

Type of functions
one to one or injective :
if f(x) = f(y) then x=y for all x and y in the domain of f
that is no two values in the domain have same value in the range
f(x**2) is not function because x and -x both will have same value
or we can say f(x)!= f(y) when f!= y helpful in proving
there may be unmapped elements in one to one we have not restricted that till now

onto or surjective
if for every element in image B there is a corresponding element in A
by definition of function there should be image for all A and from onto we have constrained all B to have preimage

one to one correspondence or bijection
if it is both one to one and onto


Inverse or Invertible  and composition of function
If function is one to one and onto we can define inverse of function as f^-1(b) = a when f(a) = b
If it is not bijection then inverse would not be function at all

Let g be function from A to B and f be function from set B to set C  and range of g be subset of domain of f
The composition of function defined by
(f o g)(a) = f(g(a))
not commutative that is  (g o f)(a) != (f o g)(a)
Composition of funtion and its inverse forms identity element in either order
f^-1 o f (a) =  a and     f  o  f^-1 (a) =  a


Relation
set of ordered pair are called binary relation its subset of AxB

Number of relation on a set
if A has n elements then number of relation on A is subset of AxA since AxA has n^2 elements x and number of subsets of m elements is 2^m so there are 2^(n^2) relations on set A

Reflexive relation
A relation R on set A is reflexive if for every element a in A there is (a,a) in R
Symmetric
A relation R on set A is symmetric if (b,a) is any pair in R then we have (a,b) also in R
Antisymmetric
if there is (a,b) and (b,a) then a=b
that is it cannot have distinct a and b with this property
Transitive
if (a,b) and (b,c) then (a,c) should be in relation

Counting Relations
number of distinct reflexive relations on a set of n elements
we count reflexive relation on AxA that has n^2 elements
since all (a,a) pairs should be present for each n elements This has to be in the relation R and remaining pairs we can form from n^2-n elements So total number of relation is 2^n(n-1)
number of distinct irreflexive relations on set of n elements
its same as reflexive because  selection of diagonal elements is fixed that is they should not be selected and remaining n^2 - n elements for 2^n(n-1) number of relations

number of distinct symmetric relations
we have to count each pair (a,b) and (b,a) once since that is for each selection (a,b), (b,a) will be selected
for first element a we can select another element in n ways including the (a,a) pair
for second element b we select another element in n-1 ways  excluding the selection of a
so there are total n + n-1 + ...1 number of elements  = n(n+1)/2
or we can look at the matrix form to see that we need to select element on or above the diagonal which is n(n+1)/2
So total number of relations is 2^(n(n+1)/2)

number of antisymmetric relations
we can have a,b or b,a or none for two distinct elements
number of two distinct element subsets - C(n 2) = n(n-1)/2
and for each subset we have 3 choices therefore 3^n(n-1)/2
we can also select diagonal elements that is (a,a) so, those gives 2^n choices
Total number of relation 3^n(n-1) /2 * 2^n

Number of relations both reflexive and antisymmetric
diagonal element all has to included so single way to select them and rest we calculated above for antisymmetric that is 3^n(n-1) /2

Number of relations both irreflexive and symmetric
we can have all elements above the diagonal but not on the diagonal since we calculated for symmetric number of pairs as n(n+1)/2 we can deduct diagonal elements from this to get n(n-1)/2
so total number of relations = 2^n(n-1)/2

Combining relations
composition SoR is defined as all ordered pair where second element in R agrees with first element in S
example if R has ordered pair 2,3 and S has ordered pair 3,5 then SoR = 2,5
Power of relation is defined as
R^n = R^n-1 o R

Relation R on set A is transitive if and only if R^n is subset of R for n=1,2,3..

Closure of relation
reflexive closure is R U all diagonal elements (a,a)
symmetric closure is R U R^-1  where R^-1 is b,a whenever a,b
Transitive closure  Transitive closure of R equals connectivity relation R^*
There is pah from a to b of length n if and only if a,b is element of R^n


Transitive closure of n elements in 0-1 matrix is R* = R^1 U R^2 U ...R^n
all called union of boolean powers each boolean power takes n^2 * 2n-1 bit operations 
that is find the composite relation R o R and take union of all such
composite relation can be found by  same way we perform the matrix multiplication but
multiplication will be AND and addition will be OR


Warshalls algorithm to compute transitive closure
requires 2n^3 bit operations unlike boolean multiplication method that requires 2n^3* (n-1) bit operations
 based on construction of zero-one matrix



Congruence
a=b mod n
1)if a-b is integer multiple of n
a-b = kn or
2)a-b divides n that is a-b/n = k or
3)a mod n = b mod n that is both have the same remainder when divided by n

congruent class modulo m
a = b mod m
we find all a for which equivalent to b mod n that is a-b is integral multiple of n

when a=b we get 0/n which is divisible for a = b+m we get  (b+m - b)/m which is divisible so
[b]_m  ={b,b+m,b+2m...} U {b-m,b-2m,b-3m}

example for [13]_9 that is find a such that a=13 mod m
{13 13+9 13+2*9 ...} U {13-9 13-2*9 ....} = {13 22 31 ..}  U {4 -5 -14}

Modular exponential
find 103^45 mod 5
solution
1)we find that remainder increases  by going from  power of 1 to 2
2) we try to get to the 1 mod m
103 mod 5 = 3  mod 5  that is now we can put 3 at place of 103
103^2 mod 5 = (3)^2 mod 5 = 4 mod 5 //we can put 4 in place of 103^2
103^4 mod 5 =  (103^2)^2 mod 5 = 4^2 mod 5  = 1
now we can find 45 in terms of 4 that is 44+1
103^45 mod 5 =  (103 mod 5) (103^44 mod 5)
                       =  (3 mod 5) ((103^4)^11 mod 45) = 3

find 58^29 mod 11
58 mod 11 =3 mod 11
58^2 mod 11 = 9 mod 11
58^4
103^44 mod 5 = (103 ^ 4)^11 mod 5 =

property
1)if a = b mod m
b^n mod m = a^n  mod m

Methods for calculating modular exponention
1)calculate b^e and then find mod with that number
requires O(e) multiplications
operations takes lot of time
2)Memory efficient method
takes more number of operations but each operation takes less time making it faster
ensures that result always stays small
number of multiplications are O(e) only
but computation time decreases by O(e) from first because calculations involve much small number
3)right-to-left binary
reduces both operations and memory required
Total running time is O(log exponent)

Linear congruence theorem
ax = b mod m has solution if and only if b is divisible by gcd (a,m)
there will be exactly d solution in set {0 , 1, 2, ..n-1}
then use extended euclid algo to find all d solutions


Problem what is minimum number of ordered pair that should be chosen such that two pairs (a1,b1) and (a2,b2) in the chosen set has
a1= a2 mod 5 and b1 = b2 mod 3
Solution
we can rewrite the equation as a1 mod 5 = a2 mod 5 and b1 mod 3 = b2 mod 3
that is we need to find the ordered pair a1,b1 such that residue on mod 5 on first pair number is equal to residue from mod 5 on second pair number
number a1 will give residue {0 1 2 3 4} on mod 5 and number b1 will give residue {0 1 2} on mod 3
that is if we choose any pair like (7, 5) then residue is {2,2}
we have to find two pairs such that their residue in ordered pair is same that is if we got residue {2,3}  on first any ordered pair then there should be another set also with residue {2,3}
since there are 3*5 different pair of reside from pigeonhole principle we can deduce that there should be at least 16 pairs.



what in case of unordered pairs?


Equivalence relation
union of two equivalance relation is not equivalence relation
example R1 = congruence mod 3 and R2 = congruence mod 4 then
intersection of equivalence relation is equivalence relation
If R is transitive then R^2 =R

To prove relation is equivalence find the relation matrix
check if reflexive by diagonal elements
symmetric from symmetry of elements above and below
transitive by M^2 = M

Equivalence classes are found by finding all related elements like if relation (a,b)R(c,d) is equivalence relation if a+b = c+d
the we can find the equivalence class as
{1,2}  = {1,2} {2,1}
{1,3} = {1,3}{3,1} {2,2}
{1,4}={1,4}{4,1}{2,3}{3,2}

Partition
division non overlapping, non empty  that covers all elements
for equivalence relation, equivalence class forms partition

Number of partitions and Equivalence relation
the total number of partition of n element set is Bn Bell number
B(n+1) = {k=0 to n} C(n k)Bk

0  1    2    3    4    5    6     7
1  1    2    5   15  52  203

Partial order
reflexive
antisymmetric if aRb and bRa then a=b
transitive

called partially ordered set poset
if a and b are distinct element of partially ordered set and either a<=b or b<= a then they are comparable
if every two elements of poset are comparable it is called totally ordered
poset is called partial because some of the sets may be incomparable

well ordered set
if it is poset such that <= is total ordering and every non empty subset of S has a least element

Maximal and minimal elements of poset
Maximal if it is not less than any element of poset
greatest element is greater than every other element, its unique
element that is greater than all the elements in a subset A of poset then its called upper bound
least upper bound of subset A if x is upper bound that is less than every other upper bound of A


Lattice partially ordered set in which every element has both least upper bound and a greatest lower bound is called lattic


LCM GCD forms lattice that is each element at first level are primes like 2 3 5 and then elements above that are multiple of first level numbers like
2*2 , 2*3 , 2*5  3*2 ..
greatest upper bound gives GCD and lowest upper bound gives LCM

Problem
a)R =SxS
i)equivalence?
equivalence as reflexive symmetry and transitive fullfils
ii)poset
antisymmetry fails that is there are a,b and b,a both only if there is single element can it be partial ordered set
b)R={}
i)equivalence
not reflexive so not equivalence relation
can't be poset also

Probability - Counting, Conditional Probability and Distributions

Glossary
Countable set : A set is countable if it is finite or has same cardinality as set of natural numbers.

If E F G are three events then
1) only E occurs
 means F and G donot occur so EF'G'

2)both E and G but not F
EGF'

3) none of the event occurs
E'F'G'

4)at least one of the event occurs
(E'F'G')' => E U F U G

5)at least two events occurs
EF U EG U FG U EFG

6)all occurs
EFG

7) at most one of them occurs
exactly one of them  occurs or none occurs
EF'G' U E'FG' U E'F'G U E'F'G'

8) at most 2 of them occurs
none occurs U exactly one occurs U exactly two occurs

Observations
1) none event occurs(E'F'G') is not complement of all event occurs (EFG)

 

Fig. all event occurs

 

Fig none event occur

Inclusion and Exclusion

P(AB) : probability of events A and B occuring together (intersection)

P(A) probability of event A independent of any other event

P(A U B) = P(A) + P(B) - P(AB)
P(E U F U G) =P(E) + P(F) + P(G) - P(EF) - P(FG) - P(GE) + P(EFG)
P(at least 1 event) = 1- P(neither of 3 events occurs)

Conditional Probability
P(B/A) = P(AB)/P(A)
P(ABC) = P(A/BC)P(BC)
             = P(A/BC) P(B/C) P(C)

since we can write

P(AB) = P(B/A) P(A) or
P(AB) = P(A/B) P(B)

Some Counting problems
Problem Find number of ways in which digit 1 appears before digit 4 in permutations of number 12345

Solution

Since for any permutation number 1 will appear either before 4 or after 4,  and number of ways in which 1 can appear before 4 = number of ways in which 1 appears after 4

number of permutations = permutations in which 1 appears before 4 + permutations in which 1 appears after 4 i.e 2(n) = 5!
n=5!/2


Problem In how many of permutations of number 12345 is first digit greater than second digit

Solution1

we will look at each digit 1 2 3 4 5 at position 2 and will find number of permutations in which first digit is less than second digit 

1) second digit is 1 

no digit is less than 1 so we have 0 cases

2) second digit is 2

at first place we can have 1 and in remaining 3! i.e 1*3!

similarly

3)second digit 3 first place can be occupied by 1 2
2 * 3!

4) second digit 4
3*4!

5) second digit 5
4*3!

total permutaions in which first digit is less than second = 3!(1+2+3+4) = 10*3!
total permutations in which first digit is greater than second = 5!-10!*3! = 5!/2
1/2(5!)


Solution 2
Since for every permutation abcd (a > b)
there will be also be permutation bacd so all cases are equally likely that 1/2 of these will have first digit greater than second



Problem Suppose we randomly select a permutation from 20! permutations of  1,2,3,4, .....20. what is probability that 2 appears at earlier position than any other even number
Solution 1
for any  permutation of number say of digits 1,2,3
123
132
213
231
321
312
Probability of any digit appearing a particular position is equally likely
In above case at position 1, one, two and three all appears twice at position 2 also they appear equal number of time at other positions.

At positon 1 either one can appear or two or three so
P(1)+P(2)+P(3) = 1
and since all are equally probable we have
p=1/3

Now we look at the problem which asks for all such permutation where number 2 appears before any other even number
Since there are 10 even numbers and whatever position they occupy the digit 2 will occur as many number of times before other even numbers as any other even digit Therefore
p =1/10

Solution 2 

number will be of form even and odd like EEEEOEOE..
number of ways to select 10 positions for odd number = C(20 10)
and there are 10! possible arrangements so its 10!*C(20 10)

It leaves place for even numbers which we have to arrange such that we place 2 before any other even number since 2 can be placed in only one way that is before all remaining even numbers
Rest even numbers can be ordered in 9! ways

so number of ways to place 2 before  even numbers is  = 10! C(20 10) * 9!
Total ways to place 20 digits is 20!
P = 9!/10! =1/10

Probability  Problems
Problem An urn contains 5 red, 6 blue,8 green balls. If 3 balls are randomly selected. what is probability of drawing 3 balls of
i)same color
Sample Space: number of ways of drawing 3 balls is C(19 3)
Event Space: number of ways of drawing same color balls = number of ways of drawing 3 red balls + number of ways of drawing 3 green ball + number of ways of drawing 3 blue balls
= C(5 3) + C(6 3) + C(8 3)

without replacement
P =(C(5 3) + C(6 3) + C(8 3)) / C(19 3)

with replacement
P = (5/19)^3 + (8/3)^3 + (8/19)^3

ii)different colors
we want one ball of each color so its
C(5 1)*C(8 1)*C(6 1)
with replacement it would be
(5/19)(6/19)(8/19)

Problem If there are 12 persons in the room, what is probability that no two of them celebrate b'day in same month
Solution
Sample space : since each person can have their b'day in any of the 12 month so its (12)^12
Event space : 12*11*10 ...1 = 12!
P = 12!/12^12

Conditional Probability Problems
Problem Consider 3 urns Urn A contains 2 white and 4 red balls; urn B contains 8 white and 4 red balls and urn C contains 1 white and 3 red balls . If one ball is selected from each urn, what is probability
that ball chosen from urn A was white given that exactly 2 white balls were selected

Solution:
P(A) : probability of selecting white ball from A. similarly P(B) P(C)
P(W₂) : probability of selecting exactly two white balls independent of any other event
P(AW₂) : white ball from A and exactly one white from B and C = P(A)*P(exactly one white from B and C )


P(A|W₂) = P(AW₂)/P(W₂)

Probability of selecting exactly one white from B and C = P(BC')+P(B'C)
since B and C are independent events
its P(B)P(C') + P(B')P(C)

Probability of selecting exactly two white ball i.e P(W) =
P(ABC')+P(AB'C)+P(A'BC) = P(A)P(B)P(C')+P(A)P(B')P(C)+P(A')P(B)P(C)
since events A B and C are independent so P(ABC) =P(A)P(B)P(C)


P(A|W₂) = P(A)* (P(B)P(C') + P(B')P(C)) / P(A)P(B)P(C')+P(A)P(B')P(C)+P(A')P(B)P(C)

Problem In a college 52% are women. 5% students are majoring in CS.2% of students are women majoring in  CS.A student is selected at random what is probability
i)that student is female given that student is CS major
Solution
P(F|C) = P(FC) / P(C)
P(F) = .53  P(C) = .05
P(FC) = .02
If it had been "2% of women are majoring in CS"  we would have taken P(C|F) instead
P(F|C) = .02/.05

Problem 5% of men and .25% of women are colorblind.A color blind person is chosen at random. what is probability of this person being male.Assume equal number of men and women.
Solution
we need to find P(M|C)
P(M|C) = P(MC)/P(C)
given data is
P(C|M) = .05     P(C|W) =.0025    P(M)=P(W) =.50

P(C) = P(M)P(C|M) + P(W)P(C|W)
P(MC)= P(C/M)P(M)

           
Observation
When probability is given like t% of A are B
it means P(B|A), when A is the sample space then it becomes P(B)
Like in the problem above when it says
5% of student are women, we are given P(W|S) i.e P(W)
.25% of women are colorblind, we have P(C|W)


Problem Stores A, B and  C have 50, 75 and 100 employees, and, respectively, 50, 60 and 70% of these are women. Resignations are equally likely among all employees, regardless of sex.One employee resigns and this is woman. what is probability that she works in store C
Solution we need to find P(C|W)
P(C|W) = P(CW)/P(W)

given data is
P(W|A) = .50    P(W|B) = .60   P(W|C) =.70
n(A) = 50          n(B)=75           n(C)=100

P(W) = P(AW) + P(BW) + P(CW)
         = P(W|A)P(A) + P(W|B)P(B)+P(W|C)P(C)

P(A) = n(A) / (n(A)+n(B)+n(C)) similarly for P(B) and P(C)

P(CW)= P(W|C)P(C)



Problem Two cards are chosen at random without replacement
Events: B both cards are ace, A ace of spades is chosen, C atleast one ace is chosen
Find P(B/A),P(B/C)

Solution

 P(B/A) probability that both cards are ace when given that ace of spade is chosen

P(B/A) = P(AB)/P(A) = |AB| / |A|

|A| is number of outcomes in which ace of spades is chosen out of 2 chosen cards = 1*51
since there are two possibilites for ace of spade, it can be first or second card so  2*51 outcomes
|AB| = choose ace of spades and one other spade from remaining 3 = 1*3
and ace of spade can be first or second card so 2*1*3

P(B/A) = 3/51

ii)P(B/C) = P(BC)/P(C) =|BC|/|C|
here lets take case when order doesnot matters whether its first ace or second
Atleast one ace means total hands of card - none ace card
= (52 2) - (48 2) = 198
or we can find exactly one ace + exactly two ace to get atleas one ace
P(B/C) = (4 2) / 198

Some terminology
Probability Distribution(pd)
pd of a random variable X is description of the probabilities associated with possible values of X
sum(P(X=i)) = 1 ; for all possible values of X
that is sum of probability distribution over all the values of random variable is always 1
problems on Probability density
www.ma.utexas.edu/users/geir/teaching/m362k/dailyhw9solns.pdf   

Probability mass function(pmf)
PD can be described by function that specifies probability at each possible value of X
f_X(x) = P(X=x)

Variance of X
sum{over all random values} x^2f(x) - (Ex)^2

Var(X) = E[ (X - E(X))²] = E(X²) - E(X)²
 Properties of Variance
E(cX) = cE(X)
E(c) =c
E(X+Y)=E(X)+E(Y)
var(c) = 0
var(cx)=c^2 * var(x)
var(x+y) = var(x) + var(y) if x and y are independent


 Probability Distributions

Bernoulli Trial and Binomial distribution

Each performance of an experiment with only two independent outcome is bernoulli trial

Probability of k success in n independent trials
For n independent trial where result is either Failure or Success we have bijection with bitstring, let 1 represent success and 0 failure then in bit string of size n we need to have exactly k 1's which is C(n k)
and probability for n trials will be p^kq^n-k
binomial distribution b(k,n,p) = C(n k)p^kq^n-k

Fig Bernoulli trial

Expected Value and Variance of B(n,p)

If X is binomial random variable with probability p and total experiment n then expected value and variance depends on p and n only with following equation

E(X) = np  because each trial results in random value 1 and 0 so mean for single trial is
1*p+0*(1-p )= p so for n trial its np
 and Variance = np(1-p)
because variance for single trial is (x-u)^2 *f(x) that is (1-p)^2*p+(0-p)^2 * (1-p) =p(1-p)

Geometric Distribution 

Instead of fixed number of trials as in bernoulli here trials are conducted until success is obtained
In Bernoulli trial we have k success but here we run the trial until first success

When we have n-1 failures and 1 success on nth trial we have probability as
(1-p)^n-1*p this is known as geometric distribution
for x = 1,2,3 ..

distribution is
x        p(x)
----------
1       p
2       (1-p)p
3        (1-p)^2*p
4        (1-p)^3 * p
.
n         (1-p)^n-1 * p

Sum of probabilities
when infinite number of trials
sum(0;-) ( p+(1-p)p+(1-p)^2 * p .................... )    = 1
when k failures and then success
sum(0;k)P(X=r) = ( p+(1-p)p+(1-p)^2 * p ...................(1-p)^k * p)    = 1- (1-p)^k+1

Expected Value
E(x) = (i=1 to n)xP(x)
       = p + 2(1-p)p + 3 (1-p)^2 p + .......n(1-p)^n-1 p
multiply both side by (1-p)
(1-p)E(x) = (1-p)p + 2(1-p)^2 p + 3 (1-p)^2 p + .......n(1-p)^n p)
subtracting 2 from 1
E(x)  - (1-p)E(x) = p + (1-p)p + (1-p)^2 p ............n(1-p)^n p)
consider n to be infinity
pE(x) =  p(1+(1-p) + (1-p)^2+ ,...........)
          = p(1/p)
E(x) = 1/p

Variance is (1-p)/(p)^2

Negative Binomial distribution 
until  r success from n trials
E(x) = r/p and Variance = r(1-p)/p^2
f(x) = C(x-1,r-1)(1-p)^x-r * p^r

Hypergeometric Distribution

Problems on Random Variable and Expected Value

Problem Two balls are chosen from the urn containing 8 white 4 black and 2 orange balls.Suppose that we win 2 points for each black ball and lose 1 point for each white ball. X denotes our winnings what are possible values of x and probability associated with each

Solution

Find sample space for 2 selected balls then find X that is winning for that selection
Lets say for selection (W,B) and (B,W) we get the wining X as +1
P(X = 1) = P(W,B)+P(B,W) = 2* 8/14*4/13  =. 3516
similarly for others we can find

Problem Consider value of random variable as

i)Find P(X>0) where P(R) = 18/38 and P(R') = 28/38
Solution P(X>0) = P(X=1) which is
P(R) + P(R'RR) assuming independent event we can write P(R'RR) = P(R')P(R)P(R)

ii)Find E(X)

E(x) = (1,n) Σ xP(X=x)
we construct probability distribution
x          P(x)
---------------------------
+1       P(R)+P(R'RR) 
-1       P(R'R'R)+P(R'RR')
-3        P(R'R'R')


Problem Consider 4 bus  carrying 40, 33, 25, 50 students resp.One of the student is selected at random Let X denote number of students in the bus carrying this randomly selected student. One of the bus driver is also randomly selected. Let Y denote number of students on this bus
Find E(X) and E(Y)

Solution 

value of X is number of students in the bus since students can be selected from any of the bus
so
x         p(x)      
----------------------
40       40/148       
33       33/148
25        25/148
50        50/148

E(x) = 39.28

Value of Y is also same as X but probability of selection of driver from a particular bus is 1/4 since there are only 4 drivers one for each bus

x         p(y)    
--------------------

40        1/4

33       1/4

25        1/4

50        1/4

Variance(X)


Problem Suppose we toss fair coin until head comes up. X represent number of tosses what is E(x)distribution
x              p
1             1/2 (H)
2             1/2*1/2 (TH)
3             1/2*1/2*1/2 (TTH) ......

E(x) = (0 to .. ) i(1/2^i)
        = 1/(1/2) = 2

Problem Each sample of water has .10 chance of containing pollutant Find probability that in next 18 sample atleast 4 contain pollutant

Solution

X number of sample that contains pollutant its bernoulli trial with p=.10 and q =.9 n =18
P(X >= 4) =   sum(x=4;18) (18 x) p^x q^18-x
or P(X>=4) = 1 - P( X < 4)



Poisson Distribution

Example
Let t be expected number of occurrence of event year
divide in to n equal intervals and assume that in any given interval the number of occurence of event is either 1 or 0 The probability of occurrence of event is then  t/n
subjected to above assumption binomial distribution gives the probability of there being r occurence of event in n intervals
The assumption is important because if two occurrences of event can happen in single interval then trinomial distribution would be required.To ensure this assumption is valid n must be sufficiently large such that the intervals are sufficiently small

P(X=r) = C(n r) (t/n)^r (1-t/n)^n-r
by solving it we get  (t^r/r!) e^-t

Sum of probabilities
(1+t/1! + t/2! + .....)e^-t  =e^t * e^-t =1


//normal distribution

Geometric Probability

Problem Two friends agree to meet at a park with the following conditions. Each will reach the park between 4 pm and 5 pm and will see if the other has already arrived. if not, they will wait for 10 minutes or the end of the hour whichever is earlier are leave. what is the probability that the two will not meet?
Solution
We do not have any discrete time intervals in this problem the event space is on real axes. we can fin d answer to such question using the plot on real axes
Let x axis represent the time line for P1 and y axis be time line for P2
points on line y=x show the time when both of them arrive at the same time
In condition we are given that they wait for interval of time 10minutes that is if P1 arrives at time t then P2 either should arrive 10min before or 10min after P1. So our region is now bounded
which is total area - 2*area of remaining triangles
that is 60*60 - 2*(1/2* (60-10)*(60-10)) = 3600 - 2500 =1100
probability is 1100/3600 = 11/36

Normal Distribution
symmetric bell shaped curve

represented as N(mean, variance) or X ~ N(m,sd^2) meaning X is normally distributed with mean m and standard deviation sd
about 2/3rd of all cases fall within one standard deviation of mean
P(mean - sd <=X <= mean+sd) = .6826
about 95% fall within 2sd
P(mean - 2sd <=X <= mean+2sd) = .9544

Standard Normal variable 
 convert into standarized normal variable
z = (x- m)/sd
this changes X in to standarized normalization with m=0 and sd =1
z ~ N(0,1)

Properties
i) p(z<=a) = f(a) when a is positive
                = 1-f(-a) when a is negative
because 1-f(a)  will be symmetrical to f(-a)  for a>0
ii)p(z>=a)  = 1-f(a)
iii)p(a<=z<=b) = f(b) -f(a)
iv)p(-a<=z<=a) = 2f(a) -1

Problem  Consider X~  N(25000, 10000^2). Find P(x<=10000))
standard variable z = (x-25000)/10000
now for x =10000 we have z = -1.5 so
p(x<=10000) = p(z<=-1.5) =1-f(1.5)

Problem In family with 11 children what is probability that there will be more boys then girls
Mean for binomial distribution is Np = 11*1/2 = 5.5
variance =Npq = 5.5*1/2 = 2.75
for binomial it is P(x>=6)
for normal we would say P(z>=5.5)

Recurrence Relations

Recurrence	Algorithm	Big-Oh Solution
T(n) = T(n/2) + O(1)	Binary Search	O(log n)
T(n) = T(n-1) + O(1)	Sequential Search	O(n)
T(n) = 2 T(n/2) + O(1)	tree traversal	O(n)
T(n) = T(n-1) + O(n)	Selection Sort (other n2 sorts)	O(n2)
T(n) = 2 T(n/2) + O(n)	Mergesort (average case Quicksort)	O(n log n)

Recurrence of form
1.T(n)= T(k) + T(n-k+1)+C
2.T(n) =T(k)+T(n-k+1)+O(n)
3.T(n)=2T(n/2) +O(n)

solution
1. O(n) , relation T(..) on right contributing also Th(n)

2. O(nlogn) ,O(n) contributing to the time complexity

3.same as 2,O(n) contributing to the time complexity

solver recurrence
1) T_n=3T_n/2       
   Tn = 3(3T_n/2²) = (3ⁱ )Tn/2ⁱ =
   3^log₂n =n^log₂3
2) Tn = 3Tn−1+2.
   3ⁿ − 1.
3) Tn = 2T(n−1) + 2.
   2ⁿ⁺¹ − 2.

Lame’s theorem (Complexity of the Euclidean algorithm). Let a and b be positive integers with a ? b, n be the number of divisions used by the Euclidean algorithm to find gcd(a, b) and k is the number of decimal digits in b. Then n <= 5k.Note that k <= log10 b?+1. Therefore, n = O(log b) divisions are used by the Euclidean algorithm.

Couting problems with Recurrence Relations

Problem Find number of bit string s with no two consecutive 0's
lets call an be number of  bit strings of lenght n where we do not  have 2 consecutive zeros
1) number of bitstrings ending with 0 that should have 1 with them, that is of the form
----|10 and the first part can be occupied by any valid bit string that itsself donot have consecutive zero that is an-2
2) number bit strings ending in 1, ----|1 which is an-1
so an = an-1 + an-2 where initial conditions should be specified for a0 a1 and a2
a0 = 0
a1=2 {0,1}
a2 = 3{01,10,11}
the recurrence seems to be like Fibonacci sequence where a1 corresponds to f3, a2 to f4  i.e  an = Fn+2
This is also relation for subsets of n numbers which do not contain consecutive number
{1,2,3} subsets are F(5) i.e {empty,{1},{2},{3},{1,3}} 5 subsets

Problem Count all number of n digit where number of zero is even
1)any number of for 9,57 which has no zero is valid, and such numbers in form of recurrence is
n-1|9 , n-1|8 , n-1|7... that is all strings ending in some non zero digit and having first n-1 as valid string
i.e 9*an-1
2)we have not counted any number which has zero digit in it ...(we use little to much recursive thinking here)
numbers with zero digit can be formed by adding a zero to number with even number of zeros
number with even number of zeros = total numbers - number with odd zeros(which we have named an)
 10^n-1 - an-1
we get final reccurence as an = 8an-1 + 10^n-1

Solving Recurrence Relations


www.cs.duke.edu/courses/cps130/.../Homeworks/Solutions/H2-solution.pdf   //order of growth problem
www.cse.psu.edu/~berman/sol_565_1.pdf

1) If f(n) = Th(g(n))  { 0<=c1g(n) <= f(n) <= c2g(n) } for some n>= n0 and c1,c2,n0 >=0 
then f(n) = O(g(n)) because it implies 0<= f(n) <= c2g(n)

2)For polynomials p(n) = Th(n^d)

3)o notation
if f(n) = o(g(n))
f(n) becomes insignificant relative to  g(n) for large values of n


4) if
f(n) = w(g(n))



Comparing various functions time complexity
5) exponential and polynomial function
exponential functions with base greater than 1 grows faster than polynomial functions that is
n^b = o(a^n) for a > 1
lim{n->infty} ( n^b / a^n)  = 0

6)exponential e^x
e = 2.71828e^x = {sum o to inty}  x^i / i!
i.e e^x  >= 1+ x
when x = 0 its equality
if |x| <=1
e^x <= 1+x+x^2
so e^x = 1+x+Th(x^2)

7)logarithm functions
polylogatithmic functions grow more slowly than polynomial in the similar manner like polynomial grows slowly than exponential
we use substitution to prove that
substitute log n for n and 2^a for a


a^(log_bc) = c^(log_ba)
 abc converts to reverse, cba


8)
Transitivity is true for all five operators like
f(n) = O(g(n)) and g(n) = O(h(n)) then
f(n) =O(h(n))

Reflexivity is also true for O,Th and Omega that is for all asymptotic tight bounds
f(n) = O((n))

Symmetry is true for Th only that is
f(n) = Th(g(n)) if and only if  gn = Th(f(n))

Case when we might not be able to compare function like in case of
trignometric functions which oscillates n^(1+sin n) and n here 1+sin n oscillates between 0 and 2