TheCATExam
Sign in

CAT 2018 Slot 1 — QA Question 29

Forming a committeeEasy

How many numbers with two or more digits can be formed with the digits 1, 2, 3, 4, 5, 6, 7, 8, 9, so that in every such number, each digit is used at most once and the digits appear in the ascending order?

Answer & solution

Answer: 502

Solution

Easy

Because the digits must appear in ascending order, choosing a set of digits fixes their arrangement — there is exactly one valid number per chosen subset. So just count subsets of {1,…,9}\{1,\dots,9\} of size ≥2\ge 2.

1

Reduce to counting subsets. An ascending number of kk digits corresponds to choosing kk digits out of 99 (order is forced). The count for each length is (9k)\binom{9}{k}.

(92)=36,(93)=84,(94)=126(95)=126,(96)=84,(97)=36(98)=9,(99)=1\begin{aligned} &\binom{9}{2}=36,\quad \binom{9}{3}=84,\quad \binom{9}{4}=126\\ &\binom{9}{5}=126,\quad \binom{9}{6}=84,\quad \binom{9}{7}=36\\ &\binom{9}{8}=9,\quad \binom{9}{9}=1 \end{aligned}
2

Sum over all lengths k=2k=2 to 99.

Total=(92)+(93)+(94)+(95)+(96)+(97)+(98)+(99)⇒ Total=36+84+126+126+84+36+9+1⇒ Total=502\begin{aligned} &\text{Total}=\binom{9}{2}+\binom{9}{3}+\binom{9}{4}+\binom{9}{5}+\binom{9}{6}+\binom{9}{7}+\binom{9}{8}+\binom{9}{9}\\ &\Rightarrow\ \text{Total}=36+84+126+126+84+36+9+1\\ &\Rightarrow\ \text{Total}=502 \end{aligned}

The total number of subsets of 99 digits is 29=5122^9=512. Remove the empty set and the 99 single-digit subsets: 512−1−9=502512-1-9=502.

Number of numbers=502\text{Number of numbers}=502
CAT 2018 Slot 1 QA Q29: How many numbers with two or more digits can be formed with the digits 1, 2, 3, 4, 5, 6, 7, 8, 9, so that in e — Solution | TheCATExam