Permutations & Combinations
Counting triplets
Grade 11
Question:
<p>The number of ways of choosing triplet \((x, y, z)\) such that \(z \geq \max\{x, y\}\) and \(x, y, z \in \{1, 2, \ldots, n, n+1\}\) is</p>
<p>\({}^{n+1}C_3 + {}^{n+2}C_3\)</p>
<p>\(n(n+1)(2n+1)/6\)</p>
<p>\(1^2 + 2^2 + \ldots + n^2\)</p>
<p>\(2\binom{n+2}{3} - {}^{n+1}C_2\)</p>
Step-by-Step Solution
Key Concept: Recognize this as a counting problem where z is a fixed maximum, then count valid (x,y) pairs below it. Use the constraint z ≥ max{x,y} to partition by z's value, and for each z, count pairs (x,y) where both are ≤ z.
<p><strong>Step 1:</strong> Interpret the constraint z ≥ max{x,y}, meaning z must be at least as large as both x and y.</p><p><strong>Step 2:</strong> Fix z ∈ {1,2,...,n+1}. For this z, both x and y must satisfy 1 ≤ x ≤ z and 1 ≤ y ≤ z.</p><p><strong>Step 3:</strong> For a fixed z, the number of valid pairs (x,y) is z·z = z² (since x has z choices and y has z choices independently).</p><p><strong>Step 4:</strong> Sum over all possible values of z:</p><p>Total = ∑(z=1 to n+1) z² = 1² + 2² + 3² + ... + (n+1)²</p><p><strong>Step 5:</strong> Apply the formula ∑(k=1 to m) k² = m(m+1)(2m+1)/6</p><p>With m = n+1:</p><p>Total = (n+1)(n+2)(2n+3)/6</p><p>∴ Answer: <strong>BC</strong></p>
Correct Answer: BC