permutations-and-combinations

Fundamental Theorem of Multiplication

• If doing a job requires doing sub job 1 and sub job 2 in that order, then the number of ways of doing the job are given by $n_{job}=n_{SJ1}\times n_{SJ}$

• LCM of two of two numbers $LCM(x^a\times y^b,x^c\times y^d)=x^{max(a,c)}\times y^{max(b,d)}$

• If a constraint is given for finding number of ways of something then start by fulfilling the that constraint

Compliment Approach

Usually it is easier to find out the number of ways when something does not happen then finding all the ways when something happens once or twice or atleast once or twice etc $n_{atleast}=total-n_{none}$ > $n_{something}=total-n_{notsomething}$

• While trying to place letters in places, if there are more places than letters to place then instead of placing letters in places, we assign places to letters

  Like: how many places can I place this letter etc etc

• Whenever repetition is allowed, always use Compliment Approach

• Two consecutive things: Just use dashes and start from above and make sure every single one as going down is different from it’s just parent

Natural Number Divisibility

Total number of natural numbers from 1 to n that are divisible by k is given by $[\frac{n}{k}]$ Here [] is greatest integer function

• Number of ways of selecting r out of n distinct objects is ${}^n{C}_r$
• Number of selections of n disticnt objects is $2^n$

Bucket Method

If you have to select things out of some other things and there are some repeating things so you canot just apply combination Make buckets of all the different things, then just make different scenarios. Like selecting all from 1 bucket and some from one and some from other etc and just add them together.

• Number of ways of arranging r distinct objects at r places is $r!$

Gap Method

When there are 2 types of objects and you want to arrange them such that same objects DO NOT COME TOGETHER then one type of objects are made to sit between the other types of objects. Just put one things in the gaps of others. Just make the first type of objects sit and find their arrangement ways, then find number of gaps and select the number of gaps needed, then arrange the second type of objects

Block Method

When there are 2 types of objects and you want to arrange them such that same objects DO COME TOGETHER then one type of objects are made into a block. Just treat the block as a single element and arrange the elements inside and outside the block

• Number of ways of arranging p elements in a row if out of p objects m and n objects are alike is given by $n=\frac{p!}{m!n!}$