Permutations and Combinations — JEE Mains Mathematics

Formulas (2)

• Together, apart and around a table · No two of k items together (row)
  $$n!\times{}^{n+1}P_{k}\quad(n\ \text{others arranged, then}\ k\ \text{items in the gaps})$$
• Repeated items, sequences and derangements · Arrangements with repeats
  $$\frac{n!}{p!\,q!\,r!\cdots}$$

Watch out for (2)

• Not together is not the same as apart
  → Together, apart and around a table
• People are distinct, floors are distinct
  → Repeated items, sequences and derangements

Formulas (2)

• The rank of a word · Rank
  $$\text{rank}=1+\sum_{i=1}^{n}c_i\,(n-i)!\quad(c_i=\text{smaller unused letters at step }i)$$
• Numbers listed in order · Block size with repetition
  $$\text{numbers after fixing }k\text{ of }n\text{ digits}=d^{\,n-k}$$

Watch out for (2)

• Repeated letters change the block size
  → The rank of a word
• Zero is allowed after the first digit
  → Numbers listed in order

Formulas (3)

• Filling positions: ranges, leading digits and no repetition · Sum of all arrangements
  $$\sum=\frac{(\text{number of arrangements})\times(\text{digit sum})}{n}\times\underbrace{11\cdots1}_{n}$$
• Divisibility conditions · Digit-sum test
  $$3\mid\overline{d_1d_2\cdots d_n}\ \text{exactly when}\ 3\mid d_1+d_2+\cdots+d_n$$
• Fixed digit sum or product · Stars and bars
  $$x_1+\cdots+x_k=S,\ x_i\ge0:\ \binom{S+k-1}{k-1}$$

Watch out for (3)

• Zero in the leading place
  → Filling positions: ranges, leading digits and no repetition
• Count the complement when it is smaller
  → Divisibility conditions
• Digits stop at 9
  → Fixed digit sum or product

Formulas (3)

• Committees and 'at least' conditions · Case sum
  $$\sum_{\text{allowed }(a,b)}\binom ma\binom nb$$
• Choosing letters from a word · One pattern
  $$\text{(choices of letters)}\times\frac{r!}{\text{(repeats)}!}$$
• Working with the nCr and nPr formulas · Telescoping
  $$\sum_{k=1}^{n}k\cdot k!=(n+1)!-1$$

Watch out for (3)

• Do not choose 'at least one' first
  → Committees and 'at least' conditions
• Distinct letters, not letter count
  → Choosing letters from a word
• Check which root is valid
  → Working with the nCr and nPr formulas

Formulas (2)

• Identical objects: stars and bars · Stars and bars
  $$x_1+\cdots+x_k=n,\ x_i\ge0:\quad\binom{n+k-1}{k-1}$$
• Distinct objects: onto maps and groups · Onto maps
  $$\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n$$

Watch out for (2)

• Distinct values are a separate count
  → Identical objects: stars and bars
• Labelled or unlabelled
  → Distinct objects: onto maps and groups

Formulas (3)

• Counting functions · One-one and increasing
  $$\#\{\text{one-one}\}={}^nP_m,\qquad\#\{\text{strictly increasing}\}=\binom nm$$
• Counting matrices by their entries · Trace of AᵀA
  $$\operatorname{tr}(A^{T}A)=\sum_{i,j}a_{ij}^{2}$$
• Subsets with a property · Complement
  $$\#\{\text{contains an even}\}=2^n-2^{\#\text{odd}}$$

Watch out for (3)

• Constrained inputs first
  → Counting functions
• Signs multiply only non-zero entries
  → Counting matrices by their entries
• The empty set
  → Subsets with a property

Formulas (2)

• Collinear points, parallel and concurrent lines · Triangles from points with collinear sets
  $$\binom n3-\sum_i\binom{k_i}{3}$$
• Triangles and diagonals in a polygon · No side of the polygon
  $$\frac{n(n-4)(n-5)}{6}$$

Watch out for (2)

• Vertices are not among the points
  → Collinear points, parallel and concurrent lines
• Indices on a circle
  → Triangles and diagonals in a polygon

Formulas (3)

• Powers of a prime in n!, and counting divisors · Legendre's formula
  $$v_p(n!)=\left\lfloor\frac np\right\rfloor+\left\lfloor\frac n{p^2}\right\rfloor+\left\lfloor\frac n{p^3}\right\rfloor+\cdots$$
• Counting multiples in a range · Inclusion–exclusion
  $$|A\cup B|=|A|+|B|-|A\cap B|$$
• Pairing numbers by their remainders · Matching classes
  $$\#\{x+y\equiv0\}=\sum_{r+s\equiv0}|C_r|\,|C_s|$$

Watch out for (3)

• The scarcer prime decides
  → Powers of a prime in n!, and counting divisors
• Use the lcm, not the product
  → Counting multiples in a range
• Ordered or unordered
  → Pairing numbers by their remainders