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.

3 comments:

  1. Hola Pedro: Buenos dias.

    Es Engelbert, de Combinatoria Aditiva. Esto del post es similar a lo que nos explicaste hoy (Metodo del Segundo Momento), verdad? Y a lo que mencionaste en el inicio del curso, que como las combinaciones son muy grandes, y que en teoría de números se usan probabilidades. Por eso se buscan estas asintotas como la de log n / 10?

    Una pregunta: Qué son funciones número-teoréticas? Lo estuve buscando la definición pero no me aparece nada con ese nombre. Pero entiendo que son funciones crecientes.

    Y otra pregunta: Que otras <> se podrían buscar relacionadas con n?

    Gracias.

    * Perdoná mi lenguaje pseudo-matemático y que mis conceptos no son claros.

    ReplyDelete
  2. ** entre llaves iba "propiedades interesantes relacionadas con n" pero no se desplegó.

    ReplyDelete
  3. Numero-teoreticas significa funciones utilizadas en teoria de numeros, generalmente definidas en base a propiedades numericas (divisores, factores primos, etc).

    Las propiedades mas estudiadas pueden ser comportamientos asintoticos, ya que estudiar la estructura real de la funcion resulta ser muy complicado.

    ReplyDelete