Suppose integers are formed by taking one or more digits from the following
2, 2, 3, 3, 4, 5, 5, 5, 6,7
For example, 355 is a possible choice while 44 is not. Find the number of distinct integers that can be formed in which
(a) the digits are non-decreasing
(b) the digits are strictly increasing
(The method I used is simply counting how many numbers with different number of digits can be formed keeping a number at the initial place but I was wondering if there is a more sophisticated way of solving this without writing so many numbers )
The given numbers can be viewed as the multiset $\{2 \cdot 2, 2 \cdot 3, 1 \cdot 4, 3 \cdot 5, 1 \cdot 6, 1 \cdot 7\}$.
Such a number is completely determined by how many times each digit appears. If we denote the number of times the digits $2, 3, 4, 5, 6, 7$ appear, respectively, by the six-tuple $(n_2, n_3, n_3, n_4, n_5, n_6, n_7)$, then the sequence $(1, 2, 0, 3, 0, 1)$ represents the integer $2335557$.
The digit $2$ can appear $0$, $1$, or $2$ times. Hence, we have three choices for $n_2$. By similar reasoning, we have three choices for $n_3$, $2$ choices for $n_4$, $4$ choices for $n_5$, $2$ choices for $n_6$, and $2$ choices for $n_7$. Hence, we have $3 \cdot 3 \cdot 2 \cdot 4 \cdot 2 \cdot 2 = 288$ choices, but one of these is empty, so there are $288 - 1 = 287$ distinct integers in which the digits are non-decreasing that can be formed from the given multiset.
Each such number is determined by whether or not we include each digit. For instance, if we include $2$, $3$, $5$, and $7$ and do not include $4$ and $6$, we obtain the integer $2357$. Since there are six possible digits, the number of choices we have is $2^6 = 64$. However, one of these uses none of the digits, so we can form $2^6 - 1 = 63$ integers with strictly increasing digits from the multiset.