¿Cuántos números de 6 dígitos son posibles con ningún dígito que aparecen más de tres veces?

Question

Cuántos de 6 dígitos de los números son posibles en la mayoría de tres dígitos repetidos?

Mi intento:

Las posibilidades son:

A)(3,2,1) Un conjunto de tres dígitos repetidos, otro conjunto de dos dígitos repetidos y otro dígito (Como, 353325, 126161)

B)(3,1,1,1) Un conjunto de tres dígitos repetidos, y tres dígitos diferentes.(Como 446394, 888764)

C)(2,2,1,1) dos conjuntos de Dos dígitos repetidos y dos dígitos diferentes (Como, 363615, 445598)

D)(2,2,2) Tres conjuntos de dos dígitos repetidos (Como, 223344, 547547)

E)(2,1,1,1,1,1) Un conjunto de dos dígitos repetidos y cuatro dígitos diferentes (Como 317653, 770986)

F)(1,1,1,1,1,1) Seis dígitos Diferentes (como 457326, 912568)

G)(3,3) Dos pares de tres dígitos repetidos. Vamos a tratar de calcular cada una de las posibilidades por separado.

F) es el más fácil de calcular.

Tratemos de entrenamiento de Caso E)

Vamos a dividir el caso en dos partes:

Caso E(1) Cero no es uno de los dígitos

Podemos elegir cualquier $5$ números forman $9$ números de $(1,2,3,\cdot, 9)$ $\binom{9}{5}$ formas , el dígito que uno se repite puede ser elegido en 5 formas, y usted puede permutar los dígitos en $\frac{6!}{2!}$ maneras. El número total de maneras en las$=\binom{9}{5}\times 5\times \frac{6!}{2!} $

Caso E(2) el Cero es uno de los dígitos.

Caso E(2)(a) Cero es la repetida dígitos que Tenemos que elegir otros cuatro números que se puede hacer en $\binom{9}{4}$ formas, los dígitos pueden ser permutados en $\frac{6!}{2!}$ maneras, pero tenemos que excluir a la vez, que comienza con el cero ($5!$ muchos). El número total de maneras =$=\binom{9}{4}\times (\frac{6!}{2!} -5!)$.

Caso E(2)(b) Cero no es el repetido dígitos que Tenemos que elegir otros cuatro números que se puede hacer en $\binom{9}{4}$ formas, las repetidas dígito puede ser elegido en 4 formas, los dígitos pueden ser permutados en $\frac{6!}{2!}$ maneras, pero tenemos que excluir a la vez, que comienza con el cero ($5!$ muchos). El número total de maneras =$=\binom{9}{4}\times 4\times (\frac{6!}{2!} -5!)$.

Antes de proceder al ejercicio de los otros casos, quiero saber

1. Es mi intento de corregir?
2. Si es correcto, es demasiado largo, hay alguna otra manera de solucionar esto?

Answer 1

Inicio: Aquí es más fácil contar el número complementario: el número de 6 dígitos enteros positivos con cuatro o más de un dígito repetido.

Esto se reduce a sólo cuatro casos: (4, 1, 1), (4, 2), (5, 1), (6).

---

El resto:

(6) es, simplemente,$9$. Estas son las $(111111, 222222, \dots, 999999)$.

(5, 1) es un poco más complicado. Primero hay $9 * 8$ formas de elegir los dos dígitos que no son cero y asignar a cada a $5$ o $1$. Luego hay ${6 \choose 1}$ formas para permutar el orden.

Ahora hay caso de que uno es igual a cero. Hay $9$ formas para elegir el dígito (no puede ser cero o más el número entero es igual a cero). Para cada combinación, no hay manera similar ${6 \choose 1}$ formas para permutar el orden. En particular, hay ${6 \choose 1}$ formas para permutar cinco ceros y uno de los otros dígitos y otro ${6 \choose 1}$ formas para permutar un cero y cinco de los otros dígitos. Exactamente la mitad de estos son válidas por simetría.

De hecho, la bijection que voltea cada dígito demuestra esta propiedad: si tenemos un mapa, por ejemplo, $aaaa0a \mapsto 0000a0$, exactamente uno de estos será válida para cada par. En este caso, tenemos $a00000, a0aaaa, aa0aaa, aaa0aa, aaaaa0a, aaaaa0$ como cadenas válidas. En total, este da

$$(9 * 8 + 9) * {6 \choose 1} = 486.$$

(4, 2) is similar. There are $9*8$ ways to initially choose and then ${6 \elegir 2}$ ways to permute the order.

If one is zero, again there are $9$ ways to choose the other digit and for each combination the number of ways to permute the order is ${6 \elegir 2}$. This is

$$(9 * 8 + 9) {6 \choose 2} = 1215.$$

Finally (4, 1, 1). There are $9 * {8 \elegir 2}$ ways to choose non-zero digits and assign them to a frequency. There are then $6! / 4!$ permutations. This gives

$$9 * {8 \choose 2} * 6! / 4! = 7560.$$

Now choose a triplet of unique digits $(a, b, c)$ where one is zero. There are ${9 \elegir 2}$ ways of doing so. Now, consider the ${6 \elija 4}$ ways to make a string from four $r$'s (r for repeated) and two $s$'s (s for single). If we are given $rsrrrs$, for example, there are now $3!$ ways to choose one of the digits as the repeated and the other two each into one $s$ spot. Of these, two are invalid, namely when we choose the repeated digit to be zero. You can convince yourself this holds for any string. Thus, this gives

$$4{9 \choose 2}{6 \choose 4} = 2160$$

The grand total is $11430$. There are $900000$ six digit numbers in total, so the desired number is $\en caja{888570}$.

---

Verified solution on computer in Python:

def get_frequencies(cycle):
    result = 0
    for num in range(10**5, 10**6):
        digit_freq = [0]*10
        for digit in get_digits(num):
            digit_freq[digit] += 1
        digit_cycle = sorted([x for x in digit_freq if x != 0], reverse=True)
        if digit_cycle == cycle:
            result += 1
    return result

def get_digits(num):
    r = []
    while num > 0:
        r.append(num % 10)
        num /= 10
    return r

Running with the following main function:

def main():
    print get_frequencies([6], 6)
    print get_frequencies([5, 1], 6)
    print get_frequencies([4, 2], 6)
    print get_frequencies([4, 1, 1], 6)

Outputs the following lines:

9
486
1215
9720

Or, more directly, we can use this program:

def get_frequency_atmost(max_freq, n):
    result = 0
    for num in range(10**(n-1), 10**n):
        digit_freq = [0]*10
        for digit in get_digits(num):
            digit_freq[digit] += 1
        if max(digit_freq) > max_freq:
            result += 1
    return 10**n - 10**(n-1) - result

which prints $888570$ en la entrada get_frequency_atmost(3, 6).

Answer 2

Voy a suponer que la pregunta significa que ningún dígito aparece más de tres veces. Como Austin Mohr señala que la pregunta está mal formulada.

Desde que el primer dígito no puede ser cero, hay $9 \cdot 10^5 = 900,000$ a los seis dígitos enteros positivos. Como Soke, voy a excluir a aquellos en los que un dígito aparece cuatro veces o más.

Consideramos los casos.

Caso 1: El mismo dígito es usado seis veces.

Desde que el primer dígito no puede ser cero, hay $9$ de estos. Son $$111 111, 222 222, 333 333, 444 444, 555 555, 666 666, 777777, 888 888, 999 999$$

Caso 2:a Un dígito se usa cinco veces, mientras que un dígito diferente se usa una vez.

Hay dos subcases.

Subcase 1: El primer dígito se repite.

Desde que el primer dígito no puede ser cero, hay nueve maneras para seleccionar el primer dígito. Debemos seleccionar cuatro de los cinco restantes lugares para colocar las otras apariciones de que el primer dígito. Luego tenemos nueve opciones para los otros dígitos desde ahora podemos usar a cero.
$$9 \cdot \binom{5}{4} \cdot 9 = 405$$

Subcase 2: El primer dígito no se repite.

Todavía tenemos nueve formas de seleccionar el primer dígito. Eso nos deja con nueve maneras de elegir los repetidos dígitos que llena el resto de los cinco lugares.
$$9 \cdot 9 = 81$$

Caso 3:a Un dígito se utiliza cuatro veces, mientras que un dígito diferente se utiliza dos veces.

Subcase 1: El primer dígito aparece cuatro veces.

Tenemos nueve formas de seleccionar el primer dígito. Tenemos $\binom{5}{3}$ formas de elección de las otras tres posiciones en las que aparece. Tenemos nueve maneras de elegir el dígito que llena las dos posiciones abiertas. $$9 \cdot \binom{5}{3} \cdot 9 = 810$$

Subcase 2: El primer dígito aparece dos veces.

Tenemos nueve formas de seleccionar el primer dígito y $\binom{5}{1}$ maneras de elegir la posición en la que aparece. Tenemos nueve opciones para la elección de los repetidos dígitos que llena las cuatro posiciones abiertas. $$9 \cdot \binom{5}{1} \cdot 9 = 405$$

Caso 4:a Un dígito se utiliza cuatro veces, mientras que los otros dos dígitos que se usan una vez cada uno.

Subcase 1: El primer dígito se repite.

Tenemos nueve formas de seleccionar el primer dígito y $\binom{5}{3}$ formas de elección de las otras tres posiciones en las que aparece. Tenemos nueve opciones de la izquierda de la posición abierta y ocho opciones para el resto de la posición. $$9 \cdot \binom{5}{3} \cdot 9 \cdot 8 = 6480$$

Subcase 2: El primer dígito no se repite.

Tenemos nueve formas de seleccionar el primer dígito. Tenemos nueve maneras de elegir los dígitos repetidos y $\binom{5}{4}$ formas de seleccionar a cuatro de los cinco posiciones abiertas en la que se coloca. Tenemos ocho maneras de llenar el resto de la posición de abierto. $$9 \cdot 9 \cdot \binom{5}{4} \cdot 8 = 3240$$

Que da un total de $$9 + 405 + 81 + 810 + 405 + 6480 + 3240 = 11,430$$ casos excluidos.

Por lo tanto, hay $$900,000 - 11,430 = 888,570$$ de seis dígitos enteros positivos en el que ningún dígito aparece más de tres veces.

Answer 3

Esto es perfectamente manejado el uso de exponenciales funciones de generación. Suponiendo primero que nos permiten tener 0 como el primer dígito (por ejemplo, estamos hablando de placas o de bloqueo de combinaciones): cada una de las $10$ dígitos pueden ocurrir hasta a $3$ a veces, y el orden de los símbolos de la materia. La respuesta es $$\left[\frac{x^6}{6!}\a la derecha] \left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\right)^{10} = 987,300.$$

Si usted desea excluir a los ceros a la izquierda, se puede restar de los de fuera. Usted que contar con la misma técnica. Si se fuerza a que el primer dígito es igual a cero, tenemos cinco dígitos restantes para seleccionar; no puede haber más de dos ceros, y hasta tres de todos los otros dígitos. Así que la cuenta es $$\left[\frac{x^5}{5!}\a la derecha] \left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\right)^9\left(1+x+\frac{x^2}{2!}\right) = 98,730.$$ Por lo tanto, el número de 6 dígitos, no comenzando desde cero, que no tengan más de 3 dígitos repetidos, es $$987,300 - 98,730 = 888,570.$$