Hallar el número de enteros distintos con dígitos no decrecientes formados a partir de uno o más de los dígitos $2, 2, 3, 3, 4, 5, 5, 5, 6, 7$

Question

Supongamos que los números enteros se forman tomando uno o más dígitos del siguientes: $2, 2, 3, 3, 4, 5, 5, 5, 6, 7$ . Por ejemplo, $355$ es una opción posible mientras que $44$ no lo es. Encuentra el número de enteros distintos que se pueden formar en los que los dígitos son no decrecientes.

Answer 1

Un número entero con dígitos no decrecientes seleccionados entre los dígitos $2, 2, 3, 3, 4, 5, 5, 5, 6, 7$ es una selección de uno o más dígitos de la cadena $2233455567$ . Por ejemplo, la selección $22\color{blue}{33}4\color{blue}{5}55\color{blue}{67}$ corresponde al número entero $33567$ .

Como los dígitos del número entero no son decrecientes, un número entero particular está completamente determinado por el número de veces que se selecciona cada dígito. Podemos seleccionar un dígito concreto hasta el número de veces que aparece en la cadena. Por ejemplo, $2$ aparece dos veces en la cadena $2233455567$ para que podamos seleccionar el dígito $2$ o bien $0$ , $1$ o $2$ veces, lo que nos da tres opciones para el número de ocurrencias del dígito $2$ en el número entero. Por un razonamiento similar, tenemos tres opciones para el número de ocurrencias del dígito $3$ en el número entero, cuatro opciones para el número de ocurrencias del dígito $5$ en el número entero, y dos opciones para el número de apariciones de cada uno de los dígitos $4$ , $6$ y $7$ . Por lo tanto, parece que el número de enteros que podemos formar con los dígitos dados es $$3 \cdot 3 \cdot 2 \cdot 4 \cdot 2 \cdot 2 = 288$$ Sin embargo, el número entero debe formarse con al menos un dígito, y hemos contado la cadena vacía. Por lo tanto, el número de enteros distintos con dígitos no decrecientes que se pueden formar a partir de permutaciones de $2, 2, 3, 3, 4, 5, 5, 5, 6, 7$ es $288 - 1 = 287$ .

Answer 2

Aquí están las enumeraciones explícitas de todas las opciones:

• Número de 1 dígito: 6 opciones ;

• Número de 2 dígitos: 18 opciones precisamente:

  • 2 dígitos diferentes = ${6 \choose 2}$ = 15 opciones;
  • 1 par de dígitos = 3 opciones;

• Número de 3 dígitos: 36 opciones precisamente:

  • 3 individuales diferentes = ${6 \choose 3}$ = 20 opciones;
  • 1 par, 1 individual diferente = $3 * 5$ = 15 opciones;
  • 1 triple = 1 elección;

• Número de 4 dígitos: 53 opciones precisamente:

  • 4 individuales diferentes = ${6 \choose 4}$ = 15 opciones;
  • 1 par, 2 individuales diferentes = 3 * ${5 \choose 2}$ = 30 opciones;
  • 2 pares: 3 opciones;
  • 1 triple, 1 simple = 1* 5 = 5 opciones;

• Número de 5 dígitos: 60 opciones precisamente:

  • 5 individuales diferentes = 6 opciones;
  • 1 par, 3 individuales diferentes = 3 * ${5 \choose 3}$ = 30 opciones;
  • 2 pares, 1 individual: 3 * 4 = 12 opciones;
  • 1 triple, 2 simples = 1* ${5 \choose 2}$ = 10 opciones;
  • 1 triple, 1 par = 2 opciones

• Ya que seleccionar un número de 6 dígitos es lo mismo que seleccionar un número de 4 dígitos para que se le quite el (único) número de 10 dígitos, la suma de opciones para el número de 6 dígitos es de nuevo 53.

• El mismo argumento para el 7, 8 y 9.

• Hay un número de 10 dígitos.

Por lo tanto, el número total de opciones es el siguiente:

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

Answer 3

Tome la cadena 2233455567.

Vamos de izquierda a derecha y para cada dígito, está dentro o está fuera. Esto nos da 2^10 enteros posibles. Excepto que tenemos un poco de doble conteo. El primer 2 y el segundo 2 fuera no es claramente diferente del primer 2 fuera y el segundo 2 dentro. Dígitos acoplados, hay 3 posibilidades (ninguno, uno, o ambos) y el triplete, tiene 4 posibilidades.

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