Permutations and Combinations — MHT-CET Maths

Formulas (3)

• The Fundamental Principle: Multiply Stages, Add Alternatives · Fundamental principle
  $$\text{stages: } m \times n \qquad \text{alternatives: } m + n$$
• nPr and nCr: Ordered Versus Unordered, and When They Are Defined · Definitions
  $${}^nP_r = \frac{n!}{(n-r)!} \qquad {}^nC_r = \frac{n!}{r!\,(n-r)!} \qquad {}^nP_r = r!\,{}^nC_r \qquad (0 \le r \le n)$$
• Identities: Pascal's Rule, Symmetry and the Ratio of Consecutive Coefficients · The three identities
  $${}^nC_r = {}^nC_{n-r} \qquad {}^nC_r + {}^nC_{r-1} = {}^{n+1}C_r \qquad \frac{{}^nC_r}{{}^nC_{r-1}} = \frac{n - r + 1}{r}$$

Watch out for (3)

• Adding stages
  → The Fundamental Principle: Multiply Stages, Add Alternatives
• Reporting an interval as the domain of nPr
  → nPr and nCr: Ordered Versus Unordered, and When They Are Defined
• Expanding the factorials
  → Identities: Pascal's Rule, Symmetry and the Ratio of Consecutive Coefficients

Formulas (4)

• Repeated Letters: Divide n! by k! for Each Repeat · Permutations of a multiset
  $$\frac{n!}{p!\,q!\,r!\cdots}$$
• Fixed Positions: Fill the Constrained Slots First, Then the Rest · Constrained slots first
  $$\text{ways} = (\text{fill constrained slots}) \times (\text{arrange what remains})$$
• Together: Glue the Group Into One Block, Then Arrange Inside It · Block method
  $$(\text{blocks})! \times \prod (\text{size of each block})!$$
• Never Together: Total Minus Together, or Place Them in the Gaps · Two routes to 'apart'
  $$\text{apart} = \text{total} - \text{together} \qquad \text{or} \qquad (\text{others})! \times {}^{k+1}P_r \ (\text{or } {}^{k+1}C_r \text{ if identical})$$

Watch out for (4)

• Counting the letters wrong
  → Repeated Letters: Divide n! by k! for Each Repeat
• Assuming four adjacent pairs remain
  → Fixed Positions: Fill the Constrained Slots First, Then the Rest
• Forgetting the inside of the block
  → Together: Glue the Group Into One Block, Then Arrange Inside It
• Using nPr for identical items in gaps
  → Never Together: Total Minus Together, or Place Them in the Gaps

Formulas (3)

• At Least and At Most: List the Cases and Add · Casework
  $$\sum_{\text{cases}} {}^{a}C_{i}\,{}^{b}C_{k-i}$$
• The Complement: Unrestricted Total Minus the Forbidden Selections · Complement
  $$\text{allowed} = \text{total} - \text{forbidden}$$
• Select the Team, Then Choose the Captain: Multiply by the Team Size · Team then role
  $$(\text{number of teams}) \times (\text{team size})$$

Watch out for (3)

• Dropping a case
  → At Least and At Most: List the Cases and Add
• Subtracting the wrong thing
  → The Complement: Unrestricted Total Minus the Forbidden Selections
• Stopping at the team count
  → Select the Team, Then Choose the Captain: Multiply by the Team Size

Formulas (3)

• (n − 1)! Around a Table, and Girls Apart via the Gaps Between Boys · Circular permutations
  $$(n - 1)! \qquad \text{girls apart: } (b - 1)! \times {}^{b}P_{g}$$
• Never Together Around a Table: Total Minus the Glued Block · Glued block on a circle
  $$(n - 1)! - (n - k)!\,k!$$
• Alternating Seats With a Couple Together, and Colouring a Circle · Cycle colourings
  $$P(C_n, k) = (k-1)^n + (-1)^n (k-1) \qquad P(C_5, 3) = 32 - 2 = 30$$

Watch out for (3)

• Using n + 1 gaps on a circle
  → (n − 1)! Around a Table, and Girls Apart via the Gaps Between Boys
• Gluing on a circle with row arithmetic
  → Never Together Around a Table: Total Minus the Glued Block
• Treating the parents' block as a row block
  → Alternating Seats With a Couple Together, and Colouring a Circle

Formulas (4)

• Digit Counting: No Leading Zero, and Divisibility by the Last Digits or the Digit Sum · Digit rules
  $$3 \mid n \iff 3 \mid \text{digit sum} \qquad 25 \mid n \iff \text{last two digits} \in \{00, 25, 50, 75\} \qquad \text{leading digit} \ne 0$$
• Inclusion–Exclusion on Multiples: gcd Conditions · Inclusion–exclusion
  $$|A \cup B| = |A| + |B| - |A \cap B|$$
• Handshakes, Diagonals and Triangle Counts: Solve an nC2 or nC3 Equation · Pairs and triples
  $$\text{handshakes} = {}^nC_2 \qquad \text{diagonals} = \frac{n(n-3)}{2} \qquad {}^{n+1}C_3 - {}^nC_3 = {}^nC_2$$
• Triangles and Quadrilaterals From Points: Subtract the Collinear Choices · Degenerate subtraction
  $$\triangle = {}^nC_3 - {}^mC_3 \qquad \text{no-side triangles of an } n\text{-gon} = \frac{n(n-4)(n-5)}{6}$$

Watch out for (4)

• Keeping the leading zero
  → Digit Counting: No Leading Zero, and Divisibility by the Last Digits or the Digit Sum
• Forgetting the add-back
  → Inclusion–Exclusion on Multiples: gcd Conditions
• Counting the sides as diagonals
  → Handshakes, Diagonals and Triangle Counts: Solve an nC2 or nC3 Equation
• Subtracting only the all-collinear picks
  → Triangles and Quadrilaterals From Points: Subtract the Collinear Choices