PYQ Vault
Ebooks

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.

Test yourself — a quick 13-question Permutation & Combination recall quiz, instant score.

Concept 1 of 3: The fundamental principle of counting

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

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

  • Legendre's formula is the trailing-zeros sum for ANY prime: the exponent of pp in n!n! is ∑k≥1⌊n/pk⌋\sum_{k\ge1}\lfloor n/p^k\rfloor. "The highest power of 5 dividing 30!+35!30!+35!" is 30!(1+31⋅32⋅33⋅34⋅35)30!(1+31\cdot32\cdot33\cdot34\cdot35); the bracket is ≡1(mod5)\equiv1\pmod5, so the answer is the exponent in 30!30!: 6+1=76+1=7. For a composite like 8=238=2^3, divide the exponent of 2 by 3 and round down.
  • Wilson's theorem: for a PRIME pp, (p−1)!≡−1(modp)(p-1)!\equiv-1\pmod p, i.e. (p−1)!+1(p-1)!+1 is divisible by pp (4!+1=254!+1=25 by 5, 6!+1=7216!+1=721 by 7). It FAILS for composite modulus (5!+1=1215!+1=121 is not divisible by 6) — a statement-check built on the composite case.

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

The same idea in a real exam question:

NDA · Sep 2019 · Q27Moderate

Example 2 · Permutation & Combination · Factorials and Binomial Coefficients

If n!n! has 17 zeros, then what is the value of nn ?

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

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.
  • Ratio of consecutive coefficients: nCr+1nCr=n−rr+1\dfrac{^nC_{r+1}}{^nC_r}=\dfrac{n-r}{r+1} — the tool for any inequality in rr: 15Cr+1>2⋅15Cr  ⟺  15−rr+1>2  ⟺  r<133^{15}C_{r+1}>2\cdot{}^{15}C_r\iff\dfrac{15-r}{r+1}>2\iff r<\tfrac{13}{3}, so the greatest such rr is 4.
  • Where nCr^nC_r is greatest: the coefficients rise then fall; the maximum is at r=n2r=\tfrac n2 for even nn, and at BOTH r=n−12r=\tfrac{n-1}{2} and r=n+12r=\tfrac{n+1}{2} (equal values) for odd nn. "Greatest iff n=2rn=2r" is therefore true only for even nn.
  • Sum and weighted sum: ∑rnCr=2n\sum_r{}^nC_r=2^n, ∑rr⋅nCr=n 2n−1\sum_r r\cdot{}^nC_r=n\,2^{n-1} (from r nCr=n n−1Cr−1r\,^nC_r=n\,^{n-1}C_{r-1}).

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

The same idea in a real exam question:

NDA · Apr 2017 · Q18Hard

Example 3 · Permutation & Combination · Factorials and Binomial Coefficients

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
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)

Test yourself on Permutation & Combination

20 past NDA questions from this chapter, timed at 25 minutes and marked the way the exam marks it. You see your score and every answer the moment you finish. Free to start.

Take the Permutation & Combination chapter testDrill all 17 questions

Related notes