Clear Notion
Login

Concepts

Read through concept notes with worked explanations and diagrams, chapter by chapter.

Concept 04 / 09Permutations and Combinations

Selections from Identical Objects and Counting Divisors

Selecting from groups of identical objects with (p + 1)(q + 1)... choices, the number of divisors of a number, sum and product of divisors, even and odd divisors, and ways to write a number as a product of two factors.

When objects of the same kind are identical, a selection is described only by how many of each kind are taken. If there are pp identical objects of one kind, qq of another and rr of a third, then from the first kind we can take 0,1,…,p0, 1, \ldots, p objects (p+1p + 1 options), and similarly for the others. So the number of selections (including taking nothing) is (p+1)(q+1)(r+1)(p + 1)(q + 1)(r + 1), and the number of non-empty selections is (p+1)(q+1)(r+1)−1(p + 1)(q + 1)(r + 1) - 1. If, in addition, there are nn distinct objects, each of those can be taken or not, contributing a factor 2n2^{n}: total (p+1)(q+1)(r+1)2n−1(p + 1)(q + 1)(r + 1)2^{n} - 1 non-empty selections. Counting divisors is exactly this problem. Every positive integer factors uniquely into primes, N=p1a1p2a2⋯pkakN = p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}. A divisor of NN is formed by choosing, for each prime, an exponent between 00 and aia_{i}, which is a selection from aia_{i} identical copies of pip_{i}. So number of divisors τ(N)=(a1+1)(a2+1)⋯(ak+1)\tau(N) = (a_{1} + 1)(a_{2} + 1)\cdots(a_{k} + 1). This includes 11 and NN. The number of proper divisors (excluding NN) is τ(N)−1\tau(N) - 1, and excluding both 11 and NN it is τ(N)−2\tau(N) - 2. Sum of divisors. Expanding the product (1+p1+⋯+p1a1)(1+p2+⋯+p2a2)⋯(1 + p_{1} + \cdots + p_{1}^{a_{1}})(1 + p_{2} + \cdots + p_{2}^{a_{2}})\cdots gives every divisor exactly once, so σ(N)=∏ipiai+1−1pi−1\sigma(N) = \prod_{i}\frac{p_{i}^{a_{i} + 1} - 1}{p_{i} - 1}. Even and odd divisors. For an odd divisor, the exponent of 22 must be 00; so if N=2aMN = 2^{a}M with MM odd, the number of odd divisors is τ(M)\tau(M), and the number of even divisors is τ(N)−τ(M)=a τ(M)\tau(N) - \tau(M) = a\,\tau(M). Similarly, divisors that are multiples of a given dd correspond to divisors of Nd\frac{N}{d} (when d∣Nd \mid N). Product of divisors. Divisors pair up as dd and Nd\frac{N}{d}, each pair multiplying to NN. With τ(N)\tau(N) divisors there are τ(N)2\frac{\tau(N)}{2} pairs, so the product of all divisors is Nτ(N)/2N^{\tau(N)/2}. This formula also works when NN is a perfect square (then τ(N)\tau(N) is odd, and N\sqrt{N} pairs with itself). Factorising into two factors. The number of ways to write NN as an ordered product a×ba \times b is τ(N)\tau(N). As an unordered product, it is τ(N)2\frac{\tau(N)}{2} if NN is not a perfect square and τ(N)+12\frac{\tau(N) + 1}{2} if it is. The number of ways to write NN as a product of two coprime factors (unordered) is 2k−12^{k - 1}, where kk is the number of distinct prime factors: each prime power goes entirely to one factor or the other. Key Takeaways: - p,q,rp, q, r identical items of three kinds: (p+1)(q+1)(r+1)(p + 1)(q + 1)(r + 1) selections, minus 11 for non-empty. - τ(p1a1⋯pkak)=∏(ai+1)\tau(p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}) = \prod(a_{i} + 1). - σ(N)=∏piai+1−1pi−1\sigma(N) = \prod\frac{p_{i}^{a_{i}+1} - 1}{p_{i} - 1}. - N=2aMN = 2^{a}M (MM odd): odd divisors τ(M)\tau(M), even divisors a τ(M)a\,\tau(M). - Product of all divisors =Nτ(N)/2= N^{\tau(N)/2}. - τ(N)\tau(N) is odd   ⟺  N\iff N is a perfect square. - Unordered factor pairs: τ(N)2\frac{\tau(N)}{2}, or τ(N)+12\frac{\tau(N) + 1}{2} for squares; coprime pairs: 2k−12^{k - 1}. - Pitfall: treating identical objects as distinct, which gives 2p+q+r2^{p+q+r} instead of (p+1)(q+1)(r+1)(p + 1)(q + 1)(r + 1). Brain-Teaser 1: How many divisors does 360360 have? How many are even, how many are multiples of 66, and what is their sum? Solution: 360=23⋅32⋅5360 = 2^{3} \cdot 3^{2} \cdot 5. So τ=4×3×2=24\tau = 4 \times 3 \times 2 = 24. Odd divisors are divisors of 45=32⋅545 = 3^{2} \cdot 5: 3×2=63 \times 2 = 6, so there are 24−6=1824 - 6 = 18 even divisors. Multiples of 66 correspond to divisors of 3606=60=22⋅3⋅5\frac{360}{6} = 60 = 2^{2} \cdot 3 \cdot 5: 3×2×2=123 \times 2 \times 2 = 12. The sum of all divisors is (1+2+4+8)(1+3+9)(1+5)=15×13×6=1170(1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 \times 13 \times 6 = 1170. Every part reduces to choosing exponents. Brain-Teaser 2: In how many ways can 1010 identical apples, 55 identical oranges and 33 distinct mangoes be selected so that at least one fruit is taken? What if at least one of each kind is required? Solution: Apples: 1111 options (00 to 1010); oranges: 66; each distinct mango: 22 (take or not), so 23=82^{3} = 8. Total selections including the empty one: 11×6×8=52811 \times 6 \times 8 = 528, so non-empty: 527527. For at least one of each kind: apples 11 to 1010 (1010 options), oranges 11 to 55 (55 options), and at least one mango (23−1=72^{3} - 1 = 7): 10×5×7=35010 \times 5 \times 7 = 350. The rule is to count options per kind and multiply, adjusting each factor for its own constraint. Brain-Teaser 3: In how many ways can 18001800 be written as a product of two positive integers (unordered)? As a product of two coprime factors? Solution: 1800=23⋅32⋅521800 = 2^{3} \cdot 3^{2} \cdot 5^{2}, so τ=4×3×3=36\tau = 4 \times 3 \times 3 = 36. 18001800 is not a perfect square (the exponent of 22 is odd), so the unordered pairs number 362=18\frac{36}{2} = 18. For coprime factors, each of the 33 prime powers 88, 99, 2525 goes wholly to one factor, giving 23=82^{3} = 8 ordered ways and 23−1=42^{3 - 1} = 4 unordered: 1×18001 \times 1800, 8×2258 \times 225, 9×2009 \times 200, 25×7225 \times 72. Pairing divisors dd with Nd\frac{N}{d} is the key to every 'product of two factors' count.

Practice this concept

Free · no account required · instant solutions

Selections from Identical Objects and Counting Divisors — DPP

4 questionsSee the solution the moment you answer

Practice