Cuántos posibles teléfono existen palabras para un número de teléfono de longitud N cuando se cuenta también con palabras de menos de longitud N dentro de ese número de teléfono?

Question

El teléfono de palabras problema

encontrar todas las palabras posibles que se pueden derivar de un teclado del teléfono, "palabras" no tiene que ser en el diccionario inglés palabras, para esta pregunta, las palabras pueden ser cualquier combinación de letras que puede ser asignado de un dígito.

Para aquellos no familiarizados, teclados de teléfono a menudo tienen cartas en la mayoría de los dígitos:

╔═════╦═════╦═════╗
║  1  ║  2  ║  3  ║
║     ║ abc ║ def ║
╠═════╬═════╬═════╣
║  4  ║  5  ║  6  ║
║ ghi ║ jkl ║ mno ║
╠═════╬═════╬═════╣
║  7  ║  8  ║  9  ║
║ pqrs║ tuv ║wxyz ║
╠═════╬═════╬═════╣
║  *  ║  0  ║  #  ║
║     ║     ║     ║
╚═════╩═════╩═════╝

Contando sólo con teléfono de palabras con una longitud de $n$

He aquí un ejemplo para tener una idea de las palabras de teléfono problema: dado un número de teléfono 366, se podría generar el siguiente teléfono de palabras

"dmm", "dmn", "dmo", "dnm", "dnn", "dno", "dom", "don", "doo", "emm", "emn", "emo", "enm", "enn", "eno", "eom", "eon", "eoo", "fmm", "fmn", "fmo", "fnm", "fnn", "fno", "fom", "fon", "foo"

Porque 3 se puede sustituir por "d", "e" o "f", y 6 se puede sustituir por "m", "n" o "s". El límite superior en el número de teléfono de palabras de longitud $n$ para un número de con $n$ dígitos es $4^n$ (la mayoría de las teclas tiene 3 letras, pero 7 y 9 mapa 4 letras).

Contando todas las palabras, hasta e incluyendo la longitud de la $n$

El ejemplo anterior nos da 27 de palabras, pero sólo somos el conteo de palabras cuya longitud es igual al número de dígitos del número de teléfono 366. Lo que si queremos encontrar todas las palabras, incluidos aquellos cuya longitud es menor que el número de teléfono? Por ejemplo, para la misma entrada como antes, 366, también se podría haber generado palabras "no", "on", "n", etc.... El número total de palabras de teléfono puede ser generado por un número de teléfono de la longitud de la $n$?

Para decirlo de otra manera

Dado un número de teléfono de la longitud de la $n$, podemos generar $4^n$ teléfono de palabras de longitud $n$, también podemos generar $2(4^{n-1})$ teléfono de palabras para cada uno de los subsectores número de teléfono con la longitud de la $n-1$ (utilizando el ejemplo anterior, que sería de todos los teléfonos palabras de 36 y 66), a continuación, todas las palabras de teléfono para todas las posibles sub números de teléfono de longitud $n-2$ etc.. Cómo muchas de las llamadas palabras están allí para un número de teléfono de la longitud de la $n$ si contamos todas las palabras de teléfono posibilidades o todas las longitudes de menos de $n$?

Intento de una respuesta

Intentar cadena de la descripción anterior en una ecuación:

$W = 4^{n} + 2(4^{n-1}) + 3(4^{n-2}) + \ldots + n$

Pero no estás seguro de dónde ir con esto.

Terminología

Número de teléfono es una secuencia ordenada de dígitos numéricos. Ejemplo: 1234560, 366 etc...

Teléfono palabra es una secuencia ordenada de latina caracteres alfabéticos (que se encuentra en En-US teléfono de teclas).

• El teléfono de cada palabra puede ser mapeada a exactamente un número de teléfono de la misma longitud. Por ejemplo: "foo" puede ser asignada a 366.
• Cada número de teléfono puede estar asignado a cero o más palabras de teléfono.

Sub número de teléfono: Dado un número de teléfono, hay $n(n+1)/2$ formas de "slice" el número en pequeños números de teléfono (sin cambiar el orden de los números). Por ejemplo: 366 contiene los siguientes sub números de teléfono: 36, 66, 3, 6, 6

Answer 1

[2015-12-10] Actualización: Gracias a un comentario de @JohnMachacek que podría incluir una referencia a un documento de probar la conjetura acerca de la estrecha límites superior.

---

Nota: Esta es una respuesta parcial a abordar algunos de límites superiores y buscando en algunos casos especiales. Pero primero me gustaría estado el problema.

Situación Actual:

Tenemos en cuenta los números de teléfono como las cadenas no vacías de construir a partir de un alfabeto $$\mathcal{A}=\{2,3,4,5,6,7,8,9\}$$ We ignore the digits $0$ and $1$ as the corresponding keys of OPs phone keypad do not contribute any alphabetical characters. Digits from $\mathcal{A}$ are mapped to either three or four characters. So, the digits are associated with weights of size $3$ or $4$.

Sólo por comodidad podemos simplificar el problema y considerar el mismo peso $m>0$ por cada dígito en $\mathcal{A}$.

OP está pidiendo el número de $\varphi(w)$ de las palabras y todas las subpalabras, que puede estar asociada con un determinado número de teléfono $w$ de la longitud de la $n$. Podemos reformular este problema por pedir que todas las subcadenas de $w$, ponderado con peso $m$ respectivamente.

Ejemplo: Si nos fijamos en los dos números de teléfono $3633$ $3336$ ambos tienen una longitud de $w=4$, se obtiene la siguiente 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 que contienen la misma dígitos junto con las mismas multiplicidades, el número de subcadenas es diferente de acuerdo a la constelación de los bloques que consiste en la igualdad de dígitos. Mientras que $3633$ tiene tres subcadenas de longitud dos, la cadena de $3336$ tiene dos subcadenas 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{blue}{2}m^2+2m\\ \end{align*}

Límites superior

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

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

• Hay en la mayoría de las $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 a $\min\{|\mathcal{A}|^k,n-k+1\}$ llegamos a la conclusión de: Una cota 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}|^k,n-k+1\right\}m^k\tag{1} \end{align*}

Si no tenemos en cuenta el tamaño de las letras del alfabeto, podemos proporcionar un cerrado expresión un poco más grande, límite superior y reclamación

La siguiente es una cota superior para $\varphi(w)$, con una longitud de $w$ igual $n$

\begin{align*} \varphi(w)\leq\frac{m\left(m^{n+1}-m(n+1)+n\right)}{(m-1)^2}\tag{2} \end{align*}

Esto es cierto, ya que de acuerdo a (1) \begin{align*} \varphi(w)&\leq\sum_{k=1}^{n}\min\left\{|\mathcal{A}|^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 la serie geométrica finita tenemos \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{m-m^{n+1}}{1-m}\right)\\ &=m\frac{nm^{n+1}-(n+1)m^n+1}{(1-m)^2} \end{align*} Poniendo estos dos resultados en (3) y la demanda (2) de la siguiente manera.

Nota: El cerrado de la expresión (2) es no necesariamente un apretado obligado. Si consideramos por ejemplo, el problema actual con un alfabeto de tamaño $7$ podemos observar la expresión (1) se produce más cerca de los límites de las palabras con la longitud de la $n>7$.

Con $|\mathcal{A}|=7$ peso y $m=3$, según los tres caracteres para cada dígito se obtiene la siguiente límites superior para valores pequeños de a $n$

\begin{array}{rcccccccccc} n&1&2&3&4&5&6&7&8&9&10\\ \text{upper bound (1)}&3&15&54&174&537&1629&4908&\color{blue}{14745}&\color{blue}{44265}&\color{blue}{132834}\\ \text{upper bound (2)}&3&15&54&174&537&1629&4908&14748&44271&132843\\ \end{array}

Apretado límites superior

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

De hecho, incluso más, es cierto. Para cada número de $n>0$ y cada alfabeto de tamaño $t>0$ la expresión en el lado derecho de (1) es un máximo.

Esto se afirma en el Teorema 8 del papel de las Cadenas con la Máxima diversas Subsecuencias y Subcadenas por A. Flaxman, et al. El máximo que puede ser alcanzado por un modificado de De Bruijn palabra.

Answer 2

A veces en este tipo de problemas, es útil considerar los algoritmos que generan la respuesta. Considere el siguiente código en python:

def num_words(phone_number):
  n = len(phone_number)
  words = []
  for i in {0, ... , n - 2}:
    for j in {i + 1, ... , n - 1}:
      words += generate_words(phone_number[i:j])
  return words

Aquí s[i:j] produce la subcadena que se ejecuta a partir del índice i índice j y generate_words(s) devuelve una lista de palabras que pueden crearse a partir de exactamente la cadena s, como en su primera lista de palabras. Debe quedar claro que este código produce la lista que desea, así que ahora sólo tenemos que averiguar cómo es grande la lista de "palabras". Supongamos que cada tecla tiene m letras, para que nuestra fórmula nos proporciona un límite inferior (en $m=3$) y un límite superior (en $m=4$). La conversión directamente desde este programa en una suma nos da $$\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}|S_{i,j}|$$ where $S_{i,j}$ is the list given by the generate words function called on a string running from index i to index j.

This is a common visualization technique in combinatorics, as computer programs that answer questions tend to make it clear how subproblems are iterated over. At each step in the program, however many words are in the list "generate_words(phone_number[i:j])" get added to the total list of words, so at every step of the sum we should be adding the corresponding quantity, which is defined to be $|S_{i,j}|$. When counting the total number of words, the for loops convert directly into summation symbols with the same bounds of summation due to the "+=".

Notice that the value of $|S_{i,j}|$ doesn't actually depend on $i,j$'s values, merely their difference. This gives us the formula (remember, assuming every key has $m$ letters): $$\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}m^{j-i}=\frac{m(m^n-mn+n-1)}{(m-1)^2}$$

Where the value of the sum is computed via Wolfram Alpha. Plugging in our values of $m$ to get upper and lower bounds yields $\frac{3}{4}(3^n-2n-1)\leq N \leq \frac{4}{9}(4^n-3n-1)$. Obtaining precise values is likely to be very hard, as introducing an indicator function for a character having options of being 4 (instead of 3) letters makes the sum impossible to simplify meaningfully, as it's rather sensitive to the exact positioning of $4$ letter numbers within the broader string.

The above implicitly assumes $n>1$, so we can separately note that the answer for $n=1$ is $m$ (as both an upper and a lower bound) and that the answer for $n=2$ es

Answer 3

Voy a restablecer algunas de las cosas que ya hemos declarado, por lo que el argumento es un poco más completa.

Tenga en cuenta que sólo voy a establecer un estricto superior y el límite inferior de la cantidad de palabras (como se define por usted).

---

Para cada número de teléfono $p_n$ de la longitud de la $n$ hay $2$ sub-números de longitud $n-1$. Cada uno de estos tienen $2$ sub-números de longitud $n-2$. Sin embargo, al menos dos de ellos son idénticos (pensemos por ejemplo $\{3415, \{341, 415\}, \{34, 41, 41, 15\}\}$. En consecuencia, el recuento de las distintas sub-números de longitud $n-2$ es de 3. Por inducción este comportamiento continúa.

Deje $w_n$ ser el límite superior de la cantidad de todos los teléfonos palabras de longitud $\ell =n$ que puede generar con un teléfono-palabra de longitud $n$. Obviamente

$$w_n = 4^n$$

Vamos, a continuación, $W_n$ ser el límite superior de la cantidad de todos los teléfonos palabras de longitud $\ell \in [1, n]$ podemos generar con teléfono-palabra de longitud $n$. Ahora podemos conseguir

$$W_n = w_n + 2\cdot w_{n-1} + 3 \cdot w_{n-2} \dots = \sum_{k=1}^{n} (n-k + 1)\cdot 4^k = (n+1)\sum_{k=1}^{n}4^k - \sum_{k=1}^{n}k\cdot4^k$$

La primera serie es una simple serie geométrica, la segunda es un poco más complicado, yo, de hecho, no está seguro de cómo resolverlo, pero mi favorito CAS me dio el siguiente resultado:

$$\begin{align} W_n &= (n+1)\sum_{k=1}^{n}4^k - \sum_{k=1}^{n}k\cdot4^k = (n+1)\cdot\underbrace{\frac{4}{3}(4^n - 1)}_{\text{First sum}} - \underbrace{\frac{4}{9}(1-4^n+3\cdot 4^n\cdot n)}_{\text{Second sum, magic}} \\ \end{align}$$

Tenga en cuenta que usted no pregunte por ella, pero voy a señalar lo que el límite inferior es, como hemos encontrado un límite superior. El límite inferior , se $\omega_n$ se produce cuando un número de teléfono es una secuencia de repetición de dígitos no es igual a $7$ o $9$. A continuación, sólo tiene $1$ único sub número, y en consecuencia:

$$\omega_n = 3^n + 3^{n-1} \dots = \sum_ {k=1}^{n}3^k = \frac{3}{2}(3^n - 1)$$

Answer 4

Hay un par de maneras de interpretar la pregunta, pero principalmente, veo dos:

1. Dado un número de teléfono específico $d_1, d_2, \dots, d_n$, $d_i$ dígitos entre el$0-9$, ¿cuántos de teléfono "palabras" ¿contiene. Más precisamente, tome el conjunto de todos los no-palabras vacías sobre la $26$ letra del alfabeto. Una $m$ palabra $w$ en este conjunto puede ser representado por $c_1, c_2, \dots, c_m$, donde cada una de las $c_i$ es uno de los $26$ letras. Se dice entonces que un número $d_1, d_2, \dots, d_n$ "contiene" una palabra $c_1, c_2, \dots, c_m$ con iff hay algunos $1 \leq i \leq j \leq n$ tal que $d_i, d_{i+1}, \dots, d_j$ corresponde a $c_1, c_2, \dots, c_m$. Se dice que una cadena de dígitos "coincide con" una cadena de caracteres (una palabra) iff escribiendo esa cadena de dígitos en un teclado de teléfono puede resultar en que la palabra (una definición más precisa es posible, pero no necesario, creo).

2. Dado el conjunto de todos los números de teléfono de longitud $n$, a partir de $\overbrace{0, 0, \dots, 0}^\text{$n$ times}$ y terminando en $\overbrace{9, 9, \dots, 9}^\text{$n$ times}$, ¿cuántas palabras de teléfono están allí, que no existe algún número de teléfono en nuestro set que contiene la palabra? Contiene es en el mismo sentido que el anterior.

Creo que el otro de dirección de las preguntas de casos $(1)$, que es por lejos el más difícil caso. La integridad, la voy a contestar caso de $(2)$ aquí, pero he de advertir a un lector de este post que la respuesta no es muy emocionante. Podemos observar simplemente que cualquier palabra de longitud de menos de $n$ está contenida en algún número de la longitud de la $n$. De hecho, está contenida en muchos un número. Para construir uno de estos números, simplemente escriba los números en el teclado del teléfono correspondiente a la palabra dada, y rellenar el resto con lo que te guste. Así pues, la cuestión se reduce a: ¿cuántas palabras de longitud $n$ o menos puede ser formado a partir de la $26$ letra del alfabeto? Hay $26$ una letra, $26^2$ dos letras, palabras, $26^3$ letra de tres palabras, y así sucesivamente. Así que la respuesta es simplemente la suma geométrica:

$$26 + 26^2 + \dots + 26^n = \dfrac{26^{n+1} - 26}{25}$$