Con este tipo de problemas puede ser útil emplear números de Stirling del segundo tipo que encapsulan la inclusión-exclusión. El recuento de recuento se simplifica bastante.
Supongamos que primero contamos $n$ -números de una, dos, tres y más cifras. cuatro dígitos diferentes donde incluimos los que empiezan por uno o más ceros. Esto viene dado por
$$\sum_{q=1}^4 {10\choose q} {n\brace q} \times q!$$
Ahora reste los números que empiezan por cero donde cero hace no aparezca por segunda vez y que tengan como máximo cuatro cifras diferentes. Esto es
$$\sum_{q=1}^4 {9\choose q-1} {n-1\brace q-1} \times (q-1)!$$
Por último, reste los que empiecen por cero cuando el cero se produzca a segunda vez o más, lo que arroja
$$\sum_{q=1}^4 {9\choose q-1} {n-1\brace q} \times q!$$
La respuesta final es
$$9\times 10^{n-1} - \left(\sum_{q=1}^4 {10\choose q} {n\brace q} \times q! - \sum_{q=1}^4 {9\choose q-1} {n-1\brace q-1} \times (q-1)! \\ - \sum_{q=1}^4 {9\choose q-1} {n-1\brace q} \times q! \right).$$
Esta fórmula se implementa en el siguiente código de Maple:
with(combinat);
Q :=
proc(n)
local res;
res :=
add(binomial(10,q)\*stirling2(n, q)\*q!, q=1..4)
- add(binomial(9,q-1)\*stirling2(n-1, q-1)\*(q-1)!, q=1..4)
- add(binomial(9,q-1)\*stirling2(n-1, q)\*q!, q=1..4);
9\*10^(n-1) - res;
end;
Se obtiene la secuencia (empezando por $n=5$ ) $$27216, 544320, 7212240, 81648000, 862774416, 8839212480, \\ 89320326480, 897169996800, 8988342579216, 89952351128640, \\ 899806333018320, \ldots$$
En particular, la respuesta para $n=10$ es
$$8839212480.$$
Los primeros valores pueden verificarse mediante el siguiente script Perl que realiza una enumeración total.
#! /usr/bin/perl -w
#
MAIN: {
my $mx = shift || 5;
for(my $n=5; $n <= $mx; $n++){
my $res = 0;
for(my $ind = 10 \*\* ($n-1); $ind < 10 \*\* $n; $ind++){
my $val = $ind, %d = ();
while($val > 0){
$d{$val % 10}++;
$val = ($val - ($val % 10))/10;
}
$res++ if scalar(keys(%d)) >= 5;
}
printf "%02d $res\\n", $n, $res;
}
}
Observación. Parece que no se gana nada trabajando con el complemento del problema. Podemos utilizar el mismo método anterior y enumerar números con cinco, seis, siete, etc. hasta diez cifras diferentes. dígitos. La siguiente rutina de Maple lo hace.
with(combinat);
Q2 :=
proc(n)
add(binomial(10,q)\*stirling2(n, q)\*q!, q=5..10)
- add(binomial(9,q-1)\*stirling2(n-1, q-1)\*(q-1)!, q=5..10)
- add(binomial(9,q-1)\*stirling2(n-1, q)\*q!, q=5..10);
end;
Forma cerrada. Podemos encontrar una forma cerrada para esta suma.
Recordemos la especie para particiones de conjuntos que es $$\mathfrak{P}(\mathcal{U} \mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ que da la función generadora $$G(z, u) = \exp(u(\exp(z)-1)).$$
El resultado es $${n\brace k} = n! [z^n] \frac{(\exp(z)-1)^k}{k!}.$$
Obtenemos así para el primer término de la suma (obsérvese que tenemos $n\ge 5$ en todo el cálculo)
$$\sum_{q=5}^{10} {10\choose q} {n\brace q} \times q! = n! [z^n] \sum_{q=5}^{10} {10\choose q} (\exp(z)-1)^q \\ = n! [z^n] \sum_{q=5}^{10} {10\choose q} \sum_{p=0}^q {q\choose p} (-1)^{q-p} \exp(pz) \\ = n! [z^n] \sum_{p=0}^{10} \exp(pz) \sum_{q=\max(5,p)}^{10} {10\choose q} {q\choose p} (-1)^{q-p} \\ = \sum_{p=0}^{10} p^n \sum_{q=\max(5,p)}^{10} {10\choose q} {q\choose p} (-1)^{q-p}.$$
El resultado es $$10^n - 210\times 4^n + 720 \times 3^n - 945 \times 2^n + 560.$$
Utilizando el mismo procedimiento obtenemos para el segundo término
$$\sum_{p=0}^{9} p^{n-1} \sum_{q=\max(4,p)}^{9} {9\choose q} {q\choose p} (-1)^{q-p}.$$
El resultado es
$$9^{n-1} - 84\times 3^{n-1} + 216\times 2^{n-1} - 189.$$
Finalmente tenemos para la tercera pieza
$$\sum_{p=0}^{10} p^{n-1} \sum_{q=\max(5,p)}^{10} {9\choose q-1} {q\choose p} (-1)^{q-p}.$$
El resultado es
$$10^{n-1} - 9^{n-1} - 84\times 4^{n-1} + 300\times 3^{n-1} - 405\times 2^{n-1} + 245.$$
Recopilando todo tenemos finalmente la forma cerrada
$$9\times 10^{n-1} - 189\times 4^n + 648\times 3^n - 1701\times 2^{n-1} + 504.$$
2 votos
El número de números de 10 cifras con sólo cuatro cifras no es $ C(10,4) \times 4^{10} $ . Esto cuenta los números con menos de cuatro dígitos más de una vez, por ejemplo $ 1231231231 $ podría obtenerse eligiendo dígitos $ 1234 $ o $ 1235 $ por lo que se cuenta varias veces.
0 votos
De acuerdo. Tendrás que prestar un poco de atención al principio de inclusión y exclusión para limpiar esto.