Find the number of distinct integers with non-decreasing digits formed from one or more of the digits $2, 2, 3, 3, 4, 5, 5, 5, 6, 7$

Question

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 the digits are non-decreasing.

Answer 1

An integer with non-decreasing digits selected from the digits $2, 2, 3, 3, 4, 5, 5, 5, 6, 7$ is a selection of one of more digits of the string $2233455567$. For instance, the selection $22\color{blue}{33}4\color{blue}{5}55\color{blue}{67}$ corresponds to the integer $33567$.

Since the digits of the integer are non-decreasing, a particular integer is completely determined by the number of times each digit is selected. We can select a particular digit up to the number of times it occurs in the string. For instance, $2$ appears twice in the string $2233455567$, so we can select the digit $2$ either $0$, $1$, or $2$ times, giving us three choices for the number of occurrences of the digit $2$ in the integer. By similar reasoning, we have three choices for the number of occurrences of the digit $3$ in the integer, four choices for the number of occurrences of the digit $5$ in the integer, and two choices for the number of occurrences of each of the digits $4$, $6$, and $7$. Hence, it would appear that the number of integers we can form with the given digits is $$3 \cdot 3 \cdot 2 \cdot 4 \cdot 2 \cdot 2 = 288$$ However, the integer must be formed using at least one digit, and we have counted the empty string. Therefore, the number of distinct integers with non-decreasing digits that can be formed from permutations of $2, 2, 3, 3, 4, 5, 5, 5, 6, 7$ is $288 - 1 = 287$.

Answer 2

Here are explicit enumerations of all choices:

• 1-digit number: 6 choices;

• 2-digit-number: 18 choices; precisely:

  • 2 single different digits = ${6 \choose 2}$ = 15 choices;
  • 1 pair of digits = 3 choices;

• 3-digit number: 36 choices; precisely:

  • 3 single different ones = ${6 \choose 3}$ = 20 choices;
  • 1 pair, 1 different single = $3 * 5$ = 15 choices;
  • 1 triple = 1 choice;

• 4-digit number: 53 choices; precisely:

  • 4 single different ones = ${6 \choose 4}$ = 15 choices;
  • 1 pair, 2 different singles = 3 * ${5 \choose 2}$ = 30 choices;
  • 2 pairs: 3 choices;
  • 1 triple, 1 single = 1* 5 = 5 choices;

• 5-digit number: 60 choices; precisely:

  • 5 single different ones = 6 choices;
  • 1 pair, 3 different singles = 3 * ${5 \choose 3}$ = 30 choices;
  • 2 pairs, 1 single: 3 * 4 = 12 choices;
  • 1 triple, 2 singles = 1* ${5 \choose 2}$ = 10 choices;
  • 1 triple, 1 pair = 2 choices

• Since selecting a 6-digit number is the same as selecting a 4-digit number to be taken away from the (only one) 10-digit-number, the sum of choices for the 6-digit number is again 53.

• Same argument for 7, 8 and 9.

• There is one 10-digit number.

The overall total number of choices is hence:

$$1 + 2\cdot(6+18+36+53) + 60 = 287.$$

Answer 3

Take the string 2233455567.

We go from left to right and for each digit, is it in or is it out. This gives us 2^10 possible integers. Except we have a little it of double counting. The first 2 and the second 2 out is not distinctly different from the fist 2 out and the second 2 in. Coupled digits, there are 3 possibilities (neither, one, or both) and the triplet, has 4 possibilities.

3*3*2*4*2*2 = 288