Sunday, August 7, 2011

Reordenando Cifras

Hace unos días me reencontré con unos viejos amigos de matemática que no veía hacía un par de años, y regresando en el tráfico pensaba sobre un pequeño comentario que hicimos con Jóse Carlos al intercambiar números telefónicos.

Unos años atrás, Jóse Carlos poseía algo que todo matemático codicia: un número telefónico que es primo. Sin embargo ahora años después cuenta con otro número. Al darle mi número, le recordé que es primo, y al particionarlo en orden ascendente en pares y tríos, los números resultantes también son primos. Para mencionarme una propiedad interesante de su número, él me dijo que al realizar una permutación de este y ordenarlo a pares se obtenían que los cuatro números obtenidos eran múltiplos dos a dos.

Pensando en propiedades de números que surgían al ser reordenados, una pregunta natural es

¿de cuántas maneras se pueden reordenar las cifras de un número para obtener números distintos?

Para un número en particular, esta pregunta es fácil de calcular, por ejemplo si vemos el número 122 podemos ver que solamente se pueden reordenar sus cifras de 3 formas diferentes

122
212
221

o para el número 524, se tienen 6 formas diferentes

245
254
425
452
524
542

Sin embargo, si llamamos

$\nu(n)=$número de números distintos obtenidos al permutar las cifras de $n$

una expresión general de $\nu(n)$ resulta muy complicada de escribir, si no es que imposible, puesto que la aparición de dígitos en la expansión decimal de $n$ no es algo fácil de controlar.

Por ejemplo se tiene que la función no es monótona y alcanza valores bajos infinitamente, e.g. $\nu(11\dots 1)=1$ para cualquier cantidad de 1´s.

Como es cosa usual con funciones número-teoréticas, un segundo paso después de buscar expresiones exactas, es buscar comportamientos asintóticos.

Una forma de encontrar esta aproximación es por medio de hallar una expresión semi-explícita para $\nu(n)$.

Sea $n_i$ es número de dígitos $i$ que aparecen en la representación decimal de $n$ y $N$ el número de dígitos de $n$. Entonces

$\nu(n)=\binom{N}{n_0}\binom{N-n_0}{n_1}\binom{N-n_0-n_1}{n_2}\dots \binom{N-n_0-n_1-\dots -n_8}{n_9}$

$=\binom{N}{n_0\, n_1\, n_2\, \dots\, n_9}$

donde el término anterior es el coeficiente multinomial del número de dígitos.

Para calcular una expresión asintótica, podemos decir que para valores grandes de $n$ genéricamente se tiene que $n$ posee sus dígitos uniformemente distribuidos, por lo tanto

$N\sim \log n$

y

$n_i\sim \frac{N}{10}=\frac{\log n}{10}$

por lo tanto tenemos que $\nu(n)$ se comporta como

$\nu(n)\sim \binom{\lfloor\log n\rfloor}{\left\lfloor\frac{\log n}{10}\right\rfloor\, \left\lfloor\frac{\log n}{10}\right\rfloor\,\dots \, \left\lfloor\frac{\log n}{10}\right\rfloor}$
$=\frac{\lfloor\log n\rfloor!}{\left[\left\lfloor\frac{\log n}{10}\right\rfloor!\right]^{10}}$


Aca está la gráfica de la asíntota para $n\leq 100000$



y como se puede ver, asíntoticamente la función crece muy rápido, por lo que para valores grandes de $n$, es posible reordenar sus cifras y encontrar números con propiedades interesantes relacionadas con $n$ dada la gran cantidad de opciones disponibles.