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!.

Permutations, combinations, and their link

nPr=n!(n−r)!nCr=n!r! (n−r)!nPr= nCr⋅r!^nP_r=\dfrac{n!}{(n-r)!} \qquad ^nC_r=\dfrac{n!}{r!\,(n-r)!} \qquad ^nP_r=\,^nC_r\cdot r!

Worked example

A menu has 3 starters and 4 mains. How many starter+main meals are possible?
Practice this conceptself-check · 4 quick reps

Permutation vs combination — does order matter?

Picking a chairperson and a secretary from nn people is a permutation (nP2^nP_2, the two roles are distinct) — but picking a 2-person committee is a combination (nC2^nC_2). Always ask: 'does swapping the two chosen items give a *different* outcome?' If yes, use nPr^nP_r; if no, use nCr= nPr/r!^nC_r=\,^nP_r/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).

Trailing zeros of n!

Z(n!)=⌊n5⌋+⌊n25⌋+⌊n125⌋+⋯Z(n!)=\left\lfloor\dfrac{n}{5}\right\rfloor+\left\lfloor\dfrac{n}{25}\right\rfloor+\left\lfloor\dfrac{n}{125}\right\rfloor+\cdots

Worked example

How many trailing zeros does 25!25! have?
Practice this conceptself-check · 4 quick reps

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]

0!=10!=1, not 00

By definition 0!=10!=1 (it's the empty product, and it makes nCn=n!n! 0!=1^nC_n=\dfrac{n!}{n!\,0!}=1 work). Treating 0!=00!=0 breaks every nC0^nC_0, nCn^nC_n, and boundary case — e.g. the number of ways to choose 0 objects is nC0=1^nC_0=1 (one way: choose nothing), not 00.
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.

Binomial coefficient identities

nCr= nCn−rnCr+ nCr−1= n+1Cr∑r=0nnCr=2nr⋅nCr=n⋅n−1Cr−1^nC_r=\,^nC_{n-r} \qquad ^nC_r+\,^nC_{r-1}=\,^{n+1}C_r \qquad \sum_{r=0}^{n}{}^nC_r=2^n \qquad r\cdot{}^nC_r=n\cdot{}^{n-1}C_{r-1}

Worked example

If nC8= nC12^nC_8=\,^nC_{12}, find nn.
Practice this conceptself-check · 4 quick reps

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

Summary — formulas & gotchas at a glance

A revision cheat-sheet for the formulas and gotchas above. Click any concept name to jump back to its full explanation.

Formulas (3)

  • The fundamental principle of counting

    Permutations, combinations, and their link

    nPr=n!(n−r)!nCr=n!r! (n−r)!nPr= nCr⋅r!^nP_r=\dfrac{n!}{(n-r)!} \qquad ^nC_r=\dfrac{n!}{r!\,(n-r)!} \qquad ^nP_r=\,^nC_r\cdot r!
  • Factorials: divisibility and trailing zeros

    Trailing zeros of n!

    Z(n!)=⌊n5⌋+⌊n25⌋+⌊n125⌋+⋯Z(n!)=\left\lfloor\dfrac{n}{5}\right\rfloor+\left\lfloor\dfrac{n}{25}\right\rfloor+\left\lfloor\dfrac{n}{125}\right\rfloor+\cdots
  • Binomial coefficient identities

    Binomial coefficient identities

    nCr= nCn−rnCr+ nCr−1= n+1Cr∑r=0nnCr=2nr⋅nCr=n⋅n−1Cr−1^nC_r=\,^nC_{n-r} \qquad ^nC_r+\,^nC_{r-1}=\,^{n+1}C_r \qquad \sum_{r=0}^{n}{}^nC_r=2^n \qquad r\cdot{}^nC_r=n\cdot{}^{n-1}C_{r-1}

Watch out for (2)

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