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

Un comienzo: aquí es más fácil contar el número complementario: el número de enteros positivos de 6 dígitos con cuatro o más de un dígito repetidos.

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

---

El resto:

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

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

Ahora hay un caso donde uno es cero. Hay$9$formas de elegir el otro dígito (no puede ser cero o el número entero es cero). Para cada combinación, hay igualmente${6 \choose 1}$formas de permutar el orden. En particular, hay${6 \choose 1}$formas de permutar cinco ceros y uno del otro dígito y otro${6 \choose 1}$formas de permutar un cero y cinco del otro dígito. Exactamente la mitad de estos son válidos por simetría.

De hecho, la biyección que invierte cada dígito demuestra esta propiedad: si mapeamos, por ejemplo,$aaaa0a \mapsto 0000a0$, exactamente uno de estos será válido para cada par. En este caso, tenemos$a00000, a0aaaa, aa0aaa, aaa0aa, aaaaa0a, aaaaa0$como cadenas válidas. En total esto da

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

(4, 2) es similar. Hay$9*8$maneras de elegir inicialmente y luego${6 \choose 2}$formas de permutar el orden.

Si uno es cero, de nuevo hay$9$formas de elegir el otro dígito y para cada combinación el número de formas de permutar el orden es${6 \choose 2}$. Esto es

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

Finalmente (4, 1, 1) . Hay$9 * {8 \choose 2}$formas de elegir dígitos distintos de cero y asignarlos a una frecuencia. hay entonces$6! / 4!$permutaciones Esto da

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

Ahora elige un triplete de dígitos únicos$(a, b, c)$donde uno es cero. Hay${9 \choose 2}$formas de hacerlo. Ahora, considere la${6 \choose 4}$maneras de hacer una cadena de cuatro$r$'s (r de repetido) y dos$s$'s (s para soltero). si nos dan$rsrrrs$, por ejemplo, ahora hay$3!$formas de elegir uno de los dígitos como el repetido y los otros dos cada uno en uno$s$lugar. De estos, dos no son válidos, es decir, cuando elegimos que el dígito repetido sea cero. Puedes convencerte de que esto es válido para cualquier cadena. Así, esto da

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

el gran total es$11430$. Hay$900000$números de seis dígitos en total, por lo que el número deseado es$\boxed{888570}$.

---

Solución verificada en computadora en 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

Corriendo con la siguiente función principal:

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)

Produce las siguientes líneas:

9
486
1215
9720

O, más directamente, podemos usar este programa:

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

que imprime$888570$en la get_frequency_atmost(3, 6)entrada

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

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

Consideramos casos.

Caso 1: El mismo dígito se usa seis veces.

Como el primer dígito no puede ser cero, hay$9$de estos. Ellos son

$$111 111, 222 222, 333 333, 444 444, 555 555, 666 666, 777777, 888 888, 999 999$$

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

Hay dos subcasos.

Subcaso 1 : El primer dígito se repite.

Dado que el primer dígito no puede ser cero, hay nueve formas de seleccionar el primer dígito. Debemos seleccionar cuatro de los cinco lugares restantes para colocar las otras ocurrencias del primer dígito. Entonces tenemos nueve opciones para el otro dígito ya que ahora podemos usar cero.

$$9 \cdot \binom{5}{4} \cdot 9 = 405$$

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

Todavía tenemos nueve formas de seleccionar el primer dígito. Eso nos deja con nueve formas de elegir el dígito repetido que llena los cinco lugares restantes.

$$9 \cdot 9 = 81$$

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

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

Tenemos nueve formas de seleccionar el primer dígito. Tenemos$\binom{5}{3}$formas de elegir las otras tres posiciones en las que aparece. Tenemos nueve formas de elegir el dígito que llena las dos posiciones abiertas.

$$9 \cdot \binom{5}{3} \cdot 9 = 810$$

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

Tenemos nueve formas de seleccionar el primer dígito y$\binom{5}{1}$formas de elegir la otra posición en la que aparece. Tenemos nueve opciones para elegir el dígito repetido que llena las cuatro posiciones abiertas.

$$9 \cdot \binom{5}{1} \cdot 9 = 405$$

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

Subcaso 1 : El primer dígito se repite.

Tenemos nueve formas de elegir el primer dígito y$\binom{5}{3}$formas de elegir las otras tres posiciones en las que aparece. Tenemos nueve opciones para la posición abierta más a la izquierda y ocho opciones para la posición restante.

$$9 \cdot \binom{5}{3} \cdot 9 \cdot 8 = 6480$$

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

Tenemos nueve formas de elegir el primer dígito. Tenemos nueve formas de elegir el dígito repetido y$\binom{5}{4}$formas de seleccionar cuatro de las cinco posiciones abiertas en las que colocarlo. Tenemos ocho formas de llenar la posición abierta restante.

$$9 \cdot 9 \cdot \binom{5}{4} \cdot 8 = 3240$$

Eso 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$$ números enteros positivos de seis dígitos en los que ningún dígito aparece más de tres veces.

Esto se maneja perfectamente usando funciones generadoras exponenciales. Suponiendo primero que se nos permite tener 0 como primer dígito (por ejemplo, estamos hablando de placas o combinaciones de candados): cada uno de$10$Los dígitos pueden ocurrir hasta$3$tiempos, y el orden de los símbolos importa. La respuesta es

$$\left[\frac{x^6}{6!}\right] \left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\right)^{10} = 987,300.$$

Si desea excluir los ceros iniciales, puede restarlos. Los cuentas usando la misma técnica. Si fuerza que el primer dígito sea cero, tenemos cinco dígitos restantes para seleccionar; puede haber como máximo dos ceros restantes y hasta tres de todos los demás dígitos. Entonces el conteo es

$$\left[\frac{x^5}{5!}\right] \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 números de 6 dígitos, que no comienzan con cero, que no tienen más de 3 dígitos repetidos, es $$987,300 - 98,730 = 888,570.$$