Easy Practice — Set 1

Quick Recap — Permutations

• Factorial: $n!=n(n-1)\cdots1$, with $0!=1$.
• Fundamental principle: if a job has $m$ then $n$ independent choices, total $=m\times n$.
• Permutations (order matters): $^nP_r=\dfrac{n!}{(n-r)!}$; $^nP_n=n!$, $^nP_0=1$.
• Arrangements of $n$ distinct objects in a row $=n!$.

Beyond-NCERT JEE Formulae

These results show up routinely in JEE Main but sit just outside the NCERT core. Memorise the small numbers below; each one collapses a multi-step problem into a one-liner.

1. Derangements — no object in its own place

A derangement is a permutation in which no element occupies its original position. The count is $$D_n=n!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\cdots+\dfrac{(-1)^{n}}{n!}\right),$$ with the fast recurrence $D_n=(n-1)\left(D_{n-1}+D_{n-2}\right)$. Memorise the first five values: $D_1=0$, then $D_2=1$, $D_3=2$, $D_4=9$ and $D_5=44$.

[JEE Tip] Phrases such as "no letter in its correct envelope", "no guest gets their own hat" or "no ball in the matching box" all signal a derangement. If exactly $k$ of the $n$ objects must stay fixed, the count is ${}^{n}C_{k}\,D_{n-k}$.

2. Divisors of $N=p^{a}q^{b}r^{c}$

Start from the prime factorisation, then read off three results:

• Number of divisors: $d=(a+1)(b+1)(c+1)$.
• Sum of divisors: $\sigma=\dfrac{p^{a+1}-1}{p-1}\cdot\dfrac{q^{b+1}-1}{q-1}\cdot\dfrac{r^{c+1}-1}{r-1}$.
• Product of divisors: $N^{d/2}$, where $d$ is the number of divisors found above.

[JEE Tip] The odd divisors of $N$ are exactly the divisors of its odd part (delete every factor of $2$); the even divisors then number $d-(\text{odd divisors})$.

3. Legendre's formula — a prime inside a factorial

The exponent of a prime $p$ in $n!$ is $$E_p(n!)=\left\lfloor\dfrac{n}{p}\right\rfloor+\left\lfloor\dfrac{n}{p^{2}}\right\rfloor+\left\lfloor\dfrac{n}{p^{3}}\right\rfloor+\cdots=\sum_{i\ge 1}\left\lfloor\dfrac{n}{p^{i}}\right\rfloor,$$ a finite sum, because every term vanishes once $p^{i}>n$.

[JEE Tip] Trailing zeros of $n!$ come from factors of $10=2\times 5$; fives are rarer than twos, so the number of trailing zeros of $n!$ equals $E_5(n!)$.

4. Distributions into boxes

• $n$ distinct objects into $r$ distinct boxes, any number per box: $r^{n}$.
• $n$ identical objects into $r$ distinct boxes, each box at least one: ${}^{n-1}C_{r-1}$.
• $n$ identical objects into $r$ distinct boxes, empty boxes allowed: ${}^{n+r-1}C_{r-1}$.

[JEE Tip] "Distinct objects into distinct boxes" is a function count $r^{n}$ — each object independently chooses its box — and is not a stars-and-bars problem.

5. Sum of all numbers formed from given digits

Using $n$ distinct non-zero digits, each exactly once, the $n!$ numbers so formed add up to $$S=(n-1)!\times(\text{sum of the digits})\times\underbrace{111\ldots1}_{n\text{ ones}}.$$ Here is why: by symmetry each digit visits each of the $n$ places exactly $(n-1)!$ times, so every place-value column carries the same digit-total $(n-1)!\times(\text{sum of the digits})$.

Solved Examples — Beyond-NCERT Formulae

Example 1 — Derangement of five letters

Problem. Five letters are placed at random into five correctly addressed envelopes, one letter per envelope. In how many ways does no letter go into its own correct envelope?

Solution. With no object in its own place, this is the derangement number $D_5$: $$D_5=5!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}-\dfrac{1}{5!}\right).$$ Here $5!=120$ and the bracket equals $\dfrac{44}{120}$, so $D_5=120\times\dfrac{44}{120}=44$. The recurrence gives the same value: $D_5=5\,D_4+(-1)^{5}=5\times 9-1=44$.

Answer: $44$ ways.

Example 2 — Number and sum of divisors of 360

Problem. Find how many positive divisors $360$ has, and the sum of all of them.

Solution. Factorise $360=2^{3}\times 3^{2}\times 5$. The number of divisors is $$d=(3+1)(2+1)(1+1)=4\times 3\times 2=24.$$ The sum of the divisors is $$\sigma=\dfrac{2^{4}-1}{2-1}\times\dfrac{3^{3}-1}{3-1}\times\dfrac{5^{2}-1}{5-1}=15\times 13\times 6=1170.$$

Answer: $360$ has $24$ divisors, summing to $1170$.

Example 3 — Product of the divisors of 360

Problem. Find the product of all positive divisors of $360$.

Solution. The product of the divisors of $N$ is $N^{d/2}$, where $d$ is the number of divisors. From Example 2, $d=24$, so the product is $$360^{d/2}=360^{24/2}=360^{12}.$$

Answer: $360^{12}$.

Example 4 — Exponent of 3 in 100!

Problem. Find the highest power of $3$ that divides $100!$.

Solution. By Legendre's formula, $$E_3(100!)=\left\lfloor\dfrac{100}{3}\right\rfloor+\left\lfloor\dfrac{100}{9}\right\rfloor+\left\lfloor\dfrac{100}{27}\right\rfloor+\left\lfloor\dfrac{100}{81}\right\rfloor=33+11+3+1=48.$$ The next term $\left\lfloor\dfrac{100}{243}\right\rfloor=0$ ends the sum.

Answer: the highest power is $3^{48}$.

Example 5 — Trailing zeros of 100!

Problem. In how many zeros does $100!$ end?

Solution. A trailing zero needs a factor $10=2\times 5$, and factors of $2$ are far more plentiful than factors of $5$, so the number of trailing zeros equals the exponent of $5$: $$E_5(100!)=\left\lfloor\dfrac{100}{5}\right\rfloor+\left\lfloor\dfrac{100}{25}\right\rfloor=20+4=24.$$ The next term $\left\lfloor\dfrac{100}{125}\right\rfloor=0$ ends the sum.

Answer: $100!$ ends in $24$ zeros.

Example 6 — Distributing 10 identical balls into 3 boxes

Problem. In how many ways can $10$ identical balls be placed in $3$ distinct boxes (a) if empty boxes are allowed, and (b) if every box must hold at least one ball?

Solution. Let the three boxes hold $x_1,x_2,x_3$ with $x_1+x_2+x_3=10$.

(a) Empty boxes allowed means each $x_i\ge 0$: $${}^{10+3-1}C_{3-1}={}^{12}C_{2}=66.$$

(b) Every box non-empty means each $x_i\ge 1$: $${}^{10-1}C_{3-1}={}^{9}C_{2}=36.$$

Answer: $66$ ways when empties are allowed, and $36$ ways when no box may be empty.

Example 7 — Sum of all 4-digit numbers from {1, 2, 3, 4}

Problem. Find the sum of all $4$-digit numbers formed using the digits $1,2,3,4$, each digit used exactly once.

Solution. There are $4!=24$ such numbers and the digit sum is $1+2+3+4=10$. By symmetry each digit stands in each place $\dfrac{4!}{4}=6$ times, so every place-value column totals $6\times 10=60$. Hence $$S=(n-1)!\times(\text{digit sum})\times 1111=3!\times 10\times 1111=6\times 10\times 1111=66660.$$

Answer: $66660$.