Saltar al contenido

¿Cuántas palabras telefónicas posibles existen para un número de teléfono de longitud N cuando también se cuentan palabras de menos de longitud N dentro de ese número de teléfono?

Posteriormente a observar en varios repositorios y páginas webs de internet al terminar dimos con la resolución que te compartiremos a continuación.

Solución:

[2015-12-10] Actualizar: Gracias a un comentario de @JohnMachacek, pude incluir una referencia a un documento que prueba la conjetura sobre los límites superiores ajustados.


Nota: Esta es una respuesta parcial que aborda algunos límites superiores y analiza algunos casos especiales. Pero primero me gusta exponer el problema.

Situación actual:

Consideramos los números de teléfono como cadenas no vacías construidas a partir de un alfabeto $$ mathcal A = 2,3,4,5,6,7,8,9 $$ Ignoramos los dígitos $ 0 $ y $ 1 $ como el correspondiente keys de los teclados del teléfono OP no aportan ningún carácter alfabético. Los dígitos de $ mathcal A $ se asignan a tres o cuatro caracteres. Entonces, los dígitos están asociados con pesos de tamaño $ 3 $ o $ 4 $.

Solo por conveniencia, simplificamos el problema y consideramos el mismo peso $ m> 0 $ para cada dígito en $ mathcal A $.

OP solicita el número $ varphi (w) $ de palabras y todas las subpalabras, que se puede asociar con un número de teléfono determinado $ w $ de longitud $ n $. Podemos reformular este problema pidiendo todas las subcadenas de $ w $, ponderado con el peso $ m $ en consecuencia.

Ejemplo: Si miramos los dos números de teléfono $ 3633 $ y $ 3336 $, ambos con una longitud $ w = 4 $, obtenemos las siguientes subcadenas

begin align * 3633 & quad rightarrow quad 3633,363,633,33,36,63,3,6 \ 3336 & quad rightarrow quad 3336,333,336,33,36,3 , 6 end align *

Observamos, que incluso si las palabras contienen los mismos dígitos junto con las mismas multiplicidades, el número de subcadenas es diferente según la constelación de bloques que constan de dígitos iguales. Mientras que $ 3633 $ tiene tres subcadenas diferentes de longitud dos, el string $ 3336 $ tiene dos subcadenas diferentes de longitud dos. Obtenemos con respecto al número de subcadenas: begin align * varphi (3633) & = m ^ 4 + 2m ^ 3 + color blue 3 m ^ 2 + 2m \ varphi (3336 ) & = m ^ 4 + 2m ^ 3 + color azul 2 m ^ 2 + 2m \ end align *

Límites superiores

Encontrar una función generadora que proporcione la distribución de $ varphi (w) $ para todos los diferentes números de teléfono de longitud $ n $ está (lamentablemente) más allá del alcance de esta respuesta. Pero al menos podemos proporcionar algunos límites superiores para Todas las palabras de longitud $ n $. Si consideramos una palabra $ w $ de longitud $ n $ y una subcadena de longitud $ k, 1 leq k leq n $ existen dos limitaciones:

  • El número de subcadenas de longitud $ k $ está limitado por el tamaño del alfabeto $ mathcal A $.

  • Hay como máximo $ n-k + 1 $ subcadenas de longitud $ k $ en una palabra de longitud $ n $.

Dado que el número de subcadenas de longitud $ k $ es menor o igual $ min mathcal A $, concluimos: Un límite superior para $ varphi (w) $ con una longitud de $ w $ igual a $ n $ es begin align * varphi (w) leq sum_ k = 1 ^ n min left mathcal A m ^ k tag 1 end align *

Si no consideramos el tamaño del alfabeto, podemos proporcionar una expresión cerrada para un límite superior algo más grande y afirmar

El siguiente es un límite superior para $ varphi (w) $ con una longitud de $ w $ igual a $ n $

begin align * varphi (w) leq frac m left (m ^ n + 1 -m (n + 1) + n right) (m-1) ^ 2 etiqueta 2 end align *

Esto sostiene true ya que de acuerdo con (1) begin align * varphi (w) & leq sum_ k = 1 ^ n min left ^ k, n-k +1 right m ^ k \ & leq sum_ k = 1 ^ n (n-k + 1) m ^ k \ & = (n + 1) sum_ k = 1 ^ n m ^ k- sum_ k = 1 ^ n km ^ k tag 3 end align * Usando la fórmula para serie geométrica finita obtenemos begin align * sum_ k = 1 ^ n m ^ k & = frac 1-m ^ n + 1 1-m -1 = m frac 1- m ^ n 1-m \ sum_ k = 1 ^ n km ^ k & = m sum_ k = 1 ^ nkm ^ k-1 \ & = m frac d dm left ( sum_ k = 1 ^ nm ^ k right) \ & = m frac d dm left ( frac mm ^ n + 1 1-m right) \ & = m frac nm ^ n + 1 - (n + 1) m ^ n + 1 (1-m) ^ 2 end align * Putting estos dos resultados en (3) y la reivindicación (2) sigue.

Nota: La expresión cerrada (2) es no necesariamente un límite apretado. Si consideramos, por ejemplo, el problema actual con un alfabeto de tamaño $ 7 $, observamos que la expresión (1) produce límites más estrechos para palabras con longitud $ n> 7 $.

Con $ | mathcal A | = 7 $ y peso $ m = 3 $ de acuerdo con tres caracteres para cada dígito, obtenemos los siguientes límites superiores para valores pequeños de $ n $

comenzararray rcccccccccc n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \ text límite superior (1) & 3 & 15 & 54 & 174 & 537 & 1629 & 4908 & color blue 14745 & color blue 44265 & color blue 132834 \ text (2) & 3 & 15 & 54 & 174 & 537 & 1629 & 4908 & 14748 & 44271 & 132843 \ end array

Límites superiores estrechos

En la sección de comentarios de la secuencia OEIS A094913 una conjetura interesante afirma que el límite superior (1) es para binario alfabetos incluso un ajustado límite superior.

De hecho aún más es true. Para cada número $ n> 0 $ y cada alfabeto de tamaño $ t> 0 $ la expresión a la derecha de (1) es un máximo.

Esto se establece en el teorema 8 del artículo. Cadenas con un número máximo de subsecuencias y subcadenas por A. Flaxman, et al. El máximo se puede lograr mediante una modificación Palabra de Bruijn.

Eres capaz de auxiliar nuestro quehacer poniendo un comentario y dejando una puntuación te damos la bienvenida.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada.