Permutations & Combinations
Grade 11
Question:
<p>A positive integer n is called strictly ascending if its digits are in ascending order, e.g. 2368 and 126 are ascending numbers but 21789 is not. The number of strictly ascending numbers < 10<sup>9</sup> is</p>
<p style="display:inline">2<sup>9 </sup>+ 1</p>
<p style="display:inline">9!</p>
<p style="display:inline">2<sup>9</sup> - 1</p>
<p style="display:inline">2<sup>9</sup></p>
Step-by-Step Solution
Key Concept: The problem reduces to selecting subsets of digits from {1, 2, ..., 9} because any chosen set of k digits can be arranged in exactly one strictly ascending order.
<p>First observation in given situation is, 0 cannot occur anywhere in any number. Second observation is, say, if we want two-digit ascending numbers, we need to select two digits from 1, 2, 3, ..., 9 and write them in ascending order (i.e., we cannot permute them because of the demand of ascending numbers). These two observations lead to the required number = <sup>9</sup>C<sub>1</sub> + <sup>9</sup>C<sub>1 </sub>+ ... + <sup>9</sup>C<sub>9</sub>) - 1<br />
= 2<sup>9</sup> - 1</p>
Correct Answer: C