Permutations & Combinations
Counting Functions with Constraints
Grade 11
Question:
<p>Let <span style="font-style: italic;">A</span> = {1, 2, 3, 4}, <span style="font-style: italic;">B</span> = {1, 2, 3, 4, 5, 6, 7, 8}. The number of onto functions <span style="font-style: italic;">f</span> : <span style="font-style: italic;">B</span> → <span style="font-style: italic;">A</span> such that if <span style="font-style: italic;">x</span><sub>1</sub> > <span style="font-style: italic;">x</span><sub>2</sub>, then <span style="font-style: italic;">f</span>(<span style="font-style: italic;">x</span><sub>1</sub>) ≤ <span style="font-style: italic;">f</span>(<span style="font-style: italic;">x</span><sub>2</sub>) ∀ <span style="font-style: italic;">x</span><sub>1</sub> ∈ <span style="font-style: italic;">B</span> is <span style="font-style: italic;">N</span>. Then the sum of digits of <span style="font-style: italic;">N</span> is</p>
<p>(P) 7</p>
<p>(Q) 8</p>
<p>(R) 9</p>
<p>(S) 10</p>
Step-by-Step Solution
Key Concept: Count onto non-decreasing functions; use the bijection between onto non-decreasing sequences and compositions of 8 into 4 positive parts.
<p><strong>Solution:</strong> We need onto non-decreasing functions from B to A. An onto non-decreasing function <span style="font-style: italic;">f</span> : <span style="font-style: italic;">B</span> → <span style="font-style: italic;">A</span> assigns 8 elements to 4 values such that all 4 values are used and the sequence is non-decreasing. This corresponds to placing 3 dividers among 8-4=4 positions, giving <span style="font-style: italic;">C</span>(7, 3) = 35. Sum of digits = 3 + 5 = 8.</p>
Correct Answer: Q