Dígitos no decrecientes

Question

Se dice que un número está formado por cifras no decrecientes si todas las cifras a la izquierda de cualquier cifra son menores o iguales a esa cifra.

Por ejemplo, el número de cuatro dígitos $1234$ se compone de dígitos que no son decrecientes. Algunos otros números de cuatro dígitos que se componen de dígitos no decrecientes son $0011$ , $1111$ , $1112$ , $1122$ , $2223$ .

Tenga en cuenta que los ceros a la izquierda son necesarios: $0000$ , $0001$ , $0002$ son todos números válidos de cuatro dígitos no decrecientes.

La pregunta es

¿Cuántos números de cuatro cifras son no decrecientes?

Answer 1

Dejar $i$ corresponden al primer dígito, $j$ al segundo, $k$ a la tercera y $l$ a la cuarta, el número de números es $$\sum_{l=0}^9 \sum_{k=0}^l \sum_{j=0}^k \sum_{i=0}^j 1$$ $$= \sum_{l=0}^9 \sum_{k=0}^l \sum_{j=0}^k \binom{j+1}{1}$$ $$= \sum_{l=0}^9 \sum_{k=0}^l \binom{k+2}{2}$$ $$= \sum_{l=0}^9 \binom{l+3}{3}$$ $$= \binom{9+4}{4} = 715$$

Answer 2

Que los cuatro dígitos sean $d_1,d_2,d_3$ y $d_4$ de izquierda a derecha. Sea $a_1=d_1,a_2=d_2-d_1,a_3=d_3-d_2$ , $a_4=d_4-d_3$ y $a_5=9-d_4$ . Obsérvese que cada número no decreciente de cuatro cifras corresponde a un único $5$ -tupla $\langle a_1,a_2,a_3,a_4,a_5\rangle$ de números enteros no negativos tales que $a_1+a_2+a_3+a_4+a_5=9$ y viceversa: dado un $5$ -podemos recuperar el número porque $d_1=a_1,d_2=a_1+a_2$ , $d_3=a_1+a_2+a_3$ y $d_4=a_1+a_2+a_3+a_4$ . (El quinto número, $a_5$ , simplemente sirve para asegurar que el total es un número conocido).

El problema de contar soluciones enteras no negativas es un estándar estrellas y barras problema. El artículo de Wikipedia da una explicación decente del razonamiento implicado; la respuesta es $$\binom{9+5-1}{5-1}=\binom{13}4=715\;.$$

Answer 3

Hay 10!/(4!*6!) = 210 para obtener 4 números diferentes

Hay 3* [10!/(3!*7!)] =3*120 =360 para obtener 3 números diferentes con 1 repetido

Hay 10! /(2!*8!) = 45 para obtener 2 números diferentes con cada repetición

Hay 2* [10!/(2!*8!) ] = 2*45 =90 para obtener 2 números diferentes con 1 que se repite 3 veces

Hay 10 formas de conseguir que un número se repita 4 veces

210 +360 +45 +90 +10 = 715

Answer 4

Mi solución es un poco diferente a la respuesta de Brian, aunque utilice la misma técnica de "estrellas y barras". Dejemos que $d_1d_2d_3d_4$ sea uno de esos números y el rango de valores para cada dígito $d_i$ será [0-9]. Para cualquier combinación dada de 4 dígitos, siempre tenemos exactamente un número no decreciente. Por ejemplo: 2,5,2,4 tiene sólo una combinación de número no decreciente, es decir, 2245. Por lo tanto, nuestro problema se reduce simplemente a encontrar "el número total de combinaciones en las que se deben seleccionar 4 dígitos de un conjunto de 10 dígitos (0-9 dígitos) en los que cada dígito puede repetirse". Para cada combinación, tenemos exactamente un número no decreciente. Así que básicamente necesitamos encontrar soluciones integrales no negativas a la ecuación $x_0 + x_1 + ... +x_{9} = 4$ que resulta ser $\binom{10+4-1}{10-1}=\binom{13}4=715\;.$

Answer 5

He aquí una solución sencilla.

Es fácil observar que sólo hay una permutación de cualquier colección de 4 dígitos tal que forme una secuencia no decreciente. Por lo tanto, existe una correspondencia de uno a uno entre encontrar el número de secuencias necesarias y el número de colecciones de $4$ dígitos (se permite la repetición), es decir, elegir $4$ de $10$ dígitos con la repetición.

Representar las opciones mediante dígitos binarios. Números de $1$ representan el número de veces que se elige el dígito; $0$ representan el paso a la siguiente cifra.

Número de permutaciones de $10101010000000$ dará todas las opciones posibles que es $13\choose4$$ =715$