Lecture 5 & 6
###################################################################################
###################################################################################
9 and 12 August, 2024
(Continued from lecture 3 & 4)
'rule of product
eg. how many injective function from A to B, given |A| = n, |B| = m; ANS: mCn * n!
= mPn
'rule of sum
experiment A : m outcomes -| DISJOINT
experiment B : n outcomes _|
if one of the experiments is conducted ( dont know which) then the total possible
outcome is m + n
eg. A: m and B: n outcomes, k outcomes are common; ANS: m+n-k outcomes
eg. how many binary strings of length 8 which either begin with a 0 or end with 11;
ANS: exp(2,7) + exp(2,6) - exp(2,5)
eg. Morning Courses Evening Courses
A D
B E
C F
D
E
Choose 2 courses (cannot choose same course in morining and evening). How many
ways possible?; ANS: 5C2 + 3C2 + (5C1 * 3C1 - 2) = 26
eg. # of passwords problem,
Conditions:
1. 6,7 or 8 characters long
2. each character is either a number or a lower case letter
3. atleast 1 number in the password
ANS: (exp(36,6) - exp(26,6)) + (exp(36,7) - exp(26,7)) + (exp(36,8) -
exp(26,8))
'permutations
mPn = mCn * n! = m * m-1 * m-2 * ... * m-n+1
'combinations
mCn = (m,n) = m! / (n! * (m-n)!) NOTE: I will rarely use the parenthesis
notation for combination in these notes as it is easy to
confuse with many
things
NOTE: mCn is the number of solutions of the equation,
x1 + x2 + ... + xm = n where xi can be either 0 or 1
'combinations with repetetions (multichoose)
same as distributing n identical things into m distinct boxes
<m,n> = (m-1+n)C(m-1)
Think of it as choosing n objects from a m distinct classes of objects where you
are allowed to choose as many objects of one class as you can and are allowed to.
NOTE: <m,n> is the number of solutions of the equation, (also present in binomial
expansion of negative index)
x1 + x2 + ... + xm = n where xi E {0,1,2...,n}
eg. you are at (0,0) and want to reach (7,7). You have to do it by MOVING right 4
times and up 3 times (moving consecutively in 1 direction is considered within the
same MOVE). how many ways to do that?; ANS: PIS for 1 * PIS for 2, PIS means
positive integer solutions = 15 * 20 = 300
1: x1 + x2 + x3 + x4 = 7, (7-1)C4 = 15
2: y1 + y2 + y3 = 7 , (7-1)C3 = 20
'multinomials
'GENERALIZED GROUPING (GG) (related to the distribution lemma and multinomial
theorem):
given, n distinct objects, the number of ways to group them in ki groups of size ni
and m such sizes
grouping ways = n! / Π (exp(ni!,ki) * ki!)
NOTE: you can think this as arranging n objects in a line and then saying that the
first certain number of objects belong to one group and similarly for others.
this means that their internal arrangement within the group is immaterial
and should not be accounted for in our final answer,
hence divide by their respective size factorials to get rid of arrangement.
also if their are multiple groups of same size then even their order is
immaterial.
hence, divide by their factorials to to get rid of arrangement.
NOTE: it is the last two lines in the note above that seperate GG from MT and DL
NOTE: to distribute these groups among certain people, multiply by appropriate
factorial
'MUTLINOMIAL THEOREM (MT) (is the same as the distribution lemma)
(exp(x1+x2+x3...+xm),n) = sigma (((n!) / Π bi! ) * Π exp(xi,bi))
'DISTRIBUTION LEMMA (DL):
when n distinct objects are supposed to be distributed into m distinct boxes, such
that the ith box contains ni balls, then the number of ways to distribute that are
ways = n! / Π ni!
eg. distribute 52 cards among 4 people; ANS = 52! / exp(13!,4) / 4! * 4! = 52! /
exp(13!,4)
group 52 cards in 4 groups; ANS = 52! / exp(13!,4) / 4!
NOTE the difference between the 2 examples above
eg. distribute 52 cards among 4 players, with the following conditions,
a. one player gets all spades; ANS = 4 * 3! * (39! / exp(13!,3) / 3!)
b. each player gets one ace; ANS = 4! * (48! / exp(12!,4) / 4!) * 4!
c. both a. and b. together; ANS = 4 * (36! / exp(12!,3) / 3!) * 3! * 3!
eg. 10 policemen to be assigned duties. 5 on patrolling duty, 2 to recieve distress
calls, and 3 in reserve for emergencies. number of ways to assign duty
ANS: 10!/5!/3!/2!
eg. 4 matches from 8 players. how many ways to conduct matches? (ie no order to be
taken into account); ANS = 8!/exp(2!,4)/4!
