Sign in

NDA Maths · Permutation & Combination

Factorials & Binomial Coefficients

The building blocks of counting: the fundamental principle, factorials and their divisibility, and the nCr identities (symmetry, Pascal's rule, and the P–C relation).

All Permutation & Combination notesNDA Maths strategy

Why this matters

Every counting problem reduces to factorials and nCr. Knowing the identities — Pascal's rule, the symmetry of nCr, and trailing-zero counting — turns the chapter's algebraic questions into one-liners.

Concept 1 of 3

The fundamental principle of counting

Intuition

If a first task can be done in mm ways and a second (independent) task in nn ways, the pair can be done in m×nm\times n ways — multiply for 'and', add for 'or'. This single rule generates permutations and combinations.

Definition

Multiplication rule: independent successive choices multiply. Addition rule: mutually exclusive alternatives add. Permutation (order matters): nPr=n!(n−r)!^nP_r=\dfrac{n!}{(n-r)!}. Combination (order doesn't): nCr=n!r!(n−r)!^nC_r=\dfrac{n!}{r!(n-r)!}. The link: nPr= nCr⋅r!^nP_r=\,^nC_r\cdot r!.

Worked example

A menu has 3 starters and 4 mains. How many starter+main meals are possible?
  1. Independent choices ⇒ multiply.
  2. 3×4=123\times 4=12.
Answer:1212.
Practice this conceptself-check · 4 quick reps

Try it yourself

How many ways to pick a chairperson then a secretary from 6 people?

Practice — Level 1 (4 reps)

Quick reps to lock in the method. Try each, then check.

  1. 1.
    'And' (independent steps) → which operation?
  2. 2.
    'Or' (exclusive alternatives) → which operation?
  3. 3.
    nPr=^nP_r=?
  4. 4.
    Relation between nPr^nP_r and nCr^nC_r?
Drill 2 more on the fundamental principle of counting

Concept 2 of 3

Factorials: divisibility and trailing zeros

Intuition

Factorials grow by absorbing every integer up to nn, so questions exploit their divisibility: n!n! is divisible by everything ≤n\le n, and its trailing zeros count the factors of 5. For a sum of factorials mod kk, only the small terms survive.

Definition

n!=1⋅2⋯nn!=1\cdot2\cdots n. Trailing zeros of n!n! =⌊n/5⌋+⌊n/25⌋+⋯=\lfloor n/5\rfloor+\lfloor n/25\rfloor+\cdots (count factors of 5). **Sum mod kk:** for n!n! with nn large enough, n!≡0n!\equiv 0, so ∑n! mod k\sum n!\bmod k depends only on the first few terms (e.g. mod 8, only 0!..3!0!..3! matter).

Worked example

How many trailing zeros does 25!25! have?
  1. ⌊25/5⌋+⌊25/25⌋=5+1\lfloor 25/5\rfloor+\lfloor 25/25\rfloor=5+1.
Answer:66.
Practice this conceptself-check · 4 quick reps

Try it yourself

Find the remainder when 1!+2!+3!+⋯+50!1!+2!+3!+\cdots+50! is divided by 88.

Practice — Level 1 (4 reps)

Quick reps to lock in the method. Try each, then check.

  1. 1.
    Trailing zeros of n!n! count factors of?
  2. 2.
    Trailing zeros of 25!25!?
  3. 3.
    For n≥4n\ge 4, n! mod 8=n!\bmod 8=?
  4. 4.
    Is n!n! divisible by every integer ≤n\le n?

From the bank · past-year question

Example 2Permutation & CombinationMODERATE
If n!n! has 17 zeros, then what is the value of nn ?

[Q27 · Sep · 2019]

Drill 5 more on factorials: divisibility and trailing zeros

Concept 3 of 3

Binomial coefficient identities

Intuition

The nCrnC_r identities let you collapse messy expressions: symmetry pairs equal coefficients, and Pascal's rule telescopes sums of consecutive coefficients into a single term.

Definition

  • Symmetry: nCr= nCn−r^nC_r=\,^nC_{n-r}; so nCx= nCy⇒x=y^nC_x=\,^nC_y\Rightarrow x=y or x+y=nx+y=n.
  • Pascal's rule: nCr+ nCr−1= n+1Cr^nC_r+\,^nC_{r-1}=\,^{n+1}C_r (telescopes sums of consecutive coefficients).
  • P–C link: nPr= nCr⋅r!^nP_r=\,^nC_r\cdot r! (recover rr from P/C=r!P/C=r!).
  • AP of coefficients: nC4, nC5, nC6^nC_4,\,^nC_5,\,^nC_6 in AP gives a quadratic in nn.

Worked example

If nC8= nC12^nC_8=\,^nC_{12}, find nn.
  1. Symmetry: 8+12=n8+12=n.
  2. n=20n=20.
Answer:2020.
Practice this conceptself-check · 4 quick reps

Try it yourself

If P(n,r)=2520P(n,r)=2520 and C(n,r)=21C(n,r)=21, find rr.

Practice — Level 1 (4 reps)

Quick reps to lock in the method. Try each, then check.

  1. 1.
    nCr= nCn−r^nC_r=\,^nC_{n-r} is which property?
  2. 2.
    Pascal's rule: nCr+ nCr−1=^nC_r+\,^nC_{r-1}=?
  3. 3.
    nC8= nC12⇒n=^nC_8=\,^nC_{12}\Rightarrow n=?
  4. 4.
    Recover rr from P(n,r)P(n,r) and C(n,r)C(n,r)?

From the bank · past-year question

Example 3Permutation & CombinationHARD
The value of [C(7,0)+C(7,1)]+[C(7,1)+C(7,2)]+…+[C(7,6)+C(7,7)][C(7,0)+C(7,1)]+[C(7,1)+C(7,2)]+\ldots+[C(7,6)+C(7,7)] is

[Q18 · Apr · 2017]

Drill 8 more on binomial coefficient identities

Mastery check — 5 interleaved questions

Try each one before clicking. Questions are interleaved across the concepts above, not grouped — interleaving sharpens transfer.

Example 1Permutation & CombinationMODERATE
Consider the following statements: 1. n!3!\frac{n!}{3!} is divisible by 6, where n>3n>3 2. n!3!+3\frac{n!}{3!}+3 is divisible by 7, where n>3n>3 Which of the above statements is/are correct?

[Q48 · Apr · 2022]

Example 2Permutation & CombinationMODERATE
Consider the following statements: 1. (25)!+1(25)!+1 is divisible by 26 2. (6)!+1(6)!+1 is divisible by 7 Which of the above statements is/are correct?

[Q19 · Apr · 2023]

Example 3Permutation & CombinationEASY
If C(20,n+2)=C(20,n−2)C(20, n+2) = C(20, n-2), then what is n equal to?

[Q12 · Apr · 2019]

Example 4Permutation & CombinationMODERATE
Consider the following statements for a fixed natural number nn: 1. C(n,r)C(n,r) is greatest if n=2rn=2r 2. C(n,r)C(n,r) is greatest if n=2r−1n=2r-1 and n=2r+1n=2r+1 Which of the statements given above is/are correct?

[Q27 · Apr · 2023]

Example 5Permutation & CombinationMODERATE
Consider the following for the items that follow: Consider the sum S=0!+1!+2!+3!+4!+…+100!S=0!+1!+2!+3!+4!+\ldots+100!.
If the sum SS is divided by 60, what is the remainder?

[Q44 · Apr · 2023]

Drill every past-year question on this subtopic

17 questions from the bank — paginated, with cart and Word-export support.

Drill the 17 questions

Related notes