Relations & Functions
Non-Decreasing Functions
Grade 12
Question:
<p>Let \(A = \{1, 2, 3, 4, 5\}\) and \(B = \{-2, -1, 0, 1, 2, 3, 4, 5\}\). The number of non-decreasing functions from A to B is</p>
<p>(a) 216</p>
<p>(b) 540</p>
<p>(c) 792</p>
<p>(d) 840</p>
Step-by-Step Solution
Key Concept: Non-decreasing functions correspond to selecting 5 elements with repetition from B, which is counted using stars and bars.
<p><strong>Solution:</strong> For a non-decreasing function from A to B, we need $f(1) \leq f(2) \leq f(3) \leq f(4) \leq f(5)$. This is equivalent to choosing 5 elements (with repetition allowed) from B in non-decreasing order. The number of such functions is $\binom{8+5-1}{5} = \binom{12}{5} = 792$.</p>
Correct Answer: D