Permutations & Combinations
Circular Arrangements
Grade 11
Question:
<p>Given <math>2n</math> different objects arranged around a circle, the number of ways of choosing <math>k</math> of them so that no two of them are consecutive is equal to (where <math>0 \leq k \leq n</math>)</p>
<p>(A) <math>\frac{2n-k+1}{2n-k+1}C_k - \frac{2n-k-1}{2n-k-1}C_{k-2}</math></p>
<p>(B) <math>\frac{2n-k-1}{2n-k-1}C_{k-1}</math></p>
<p>(C) <math>\frac{2n-k}{2n-k}C_k</math></p>
<p>(D) Not specified</p>
Step-by-Step Solution
Key Concept: When selecting k objects from 2n objects arranged in a circle such that no two are consecutive, we can use a bijection with selecting k non-consecutive objects from a linear arrangement. The key is to remove the k selected objects and the k gaps between them (to ensure non-consecutiveness), leaving 2n-2k objects that can be arranged with k objects inserted among them.
<p><strong>Step 1: Set up the problem</strong></p><p>We have 2n objects in a circle and need to choose k of them such that no two chosen objects are adjacent.</p><p><strong>Step 2: Transform to a manageable form</strong></p><p>When we select k objects from a circle with no two consecutive, we can think of this as: after selecting k objects, there must be at least 1 unchosen object between any two consecutive chosen objects. This means we need k gaps (one after each chosen object in the circle).</p><p><strong>Step 3: Reduce to linear selection problem</strong></p><p>Consider the k selected objects and the k mandatory gaps between them (in circular order). These account for 2k positions. The remaining 2n - 2k objects must fill the remaining positions.</p><p><strong>Step 4: Count arrangements of unchosen objects</strong></p><p>We have 2n - 2k unchosen objects and k 'slots' (the gaps after each chosen object in the circle). We need to distribute these 2n - 2k objects into k positions such that each gap has at least 1 object (already guaranteed).</p><p><strong>Step 5: Apply stars and bars with circular constraint</strong></p><p>For a circular arrangement, we can break the circle at one point. We need to place 2n - k - 1 unchosen objects into k chosen-gaps. This becomes a problem of selecting k objects from 2n - k - 1 available positions, which equals C(2n-k-1, k-1).</p><p><strong>Step 6: Verify the formula</strong></p><p>The number of ways = $\frac{2n-k-1}{2n-k-1}C_{k-1} = C(2n-k-1, k-1)$</p><p><strong>∴ Answer:</strong> B</p>
Correct Answer: B