¿De cuántas maneras se puede escribir un número en un ábaco?

Question

Un amigo me pregunto algunas cuestiones básicas acerca de los ábacos por lo que les comparto la siguiente pregunta que me surgió y que podría ser de su agrado: dado un número x, sea f una función que cuenta el número de formas combinatoriamente distintas que se pueden escribir en un ábaco tipo europeo (diez filas cada una con 10 bolitas) tal que la primer fila cuenta las unidades, la segunda fila cuenta las decenas y así sucesivamente. Por ejemplo, f(100)=3 ya que 100 puede ser escrito de tres maneras: a) una bolita  en la tercer fila (lo podemos indicar como 1,0,0), b) diez bolitas en la segunda fila (digamos 10,0), y c) nueve bolitas en la segunda hilera y 10 en la primera (9,10).

Answer 1

Esto no es una respuesta completa, pero aquí van mis ideas. Usaré la misma notación que tú, es decir, $(a_k,a_{k-1},\ldots,a_0) $ representa a $\sum_{i=0}^k(10^ia_i)$ (con $a_i$ enteros entre 0 y 10). Dada una secuencia $s=(a_k,a_{k-1},\ldots,a_0) $ denotamos $s^*=(a_k,a_{k-1},\ldots,a_0,0)$, $s'=(a_k,a_{k-1},\ldots,a_0,10)$ y $s^-=(a_k,a_{k-1},\ldots,a_1)$ . Si $n$ es un natural, denotamos por $n^*$ al natural que se obtiene al quitarle a $n$ todos los dígitos después del último 0 en su expresión decimal.

Primero observamos que $n$ y $n^*$ se pueden representar en la misma cantidad de formas, pues los dígitos después del último 0 tienen que representarse por ellos mismos. También observamos que 0 y los números que no llevan 0 en su expresión decimal se pueden representar de una única manera.

Mi última observación es la siguiente fórmula recursiva: $f (10n)=f(n)+f (n-1)$. Esto es porque para cada secuencia $s$ que represente a $n$ se tiene que $s^*$ representa a $10n$ y para cada $s$ que representa a $n-1$ se tiene que $s'$ representa también a $10n$. Por otra parte  si $s$ representa a $10n$ se tiene que $a_0=0$ o $a_0=10$. En el primer caso se tiene que $s^-$ representa a $n $ y $(s^-)^*=s$. En el segundo caso  $s^-$ representa a $n-1$ y $(s^-)'=s$.

Si bien esto no te da una fórmula explícita te da un algoritmo rápido para calcular  $f$. Por ejemplo:

$f(1101)=f (110)=f (11)+f (10)=1+(f (1)+f (0))=1+(1+1)=3$.
 
En efecto las secuencias que representan a 1101 son $(1,1,0,1), (1,0,10,1), (9,10,10,1) $.

Comments

Probablemente se pueda usar esto para deducir una fórmula que dependa de la cantidad de ceros y unos en la expresión decimal y de cómo están acomodados, pero no la veo rápido.

---

Sólo para aclararme si entiendo bien: 100*=100? es decir, el primer cero es el de las decenas y el último cero es el de las unidades en este caso?

Sobre tu primera observación, ejemplificamos f(101)=f(10)=2. Cierto, si n es 0 o no contiene ceros en su expresión decimal entonces f(n)=1.

Cuando escribes 10n significa multiplicación, cierto?

Efectivamente, has encontrado una recursión :)

---

Sí, llamo "último dígito" al de las unidades, por lo que en efecto$100^*=100$. Y sí, $10n$ es 10 veces $n$. La idea es que si el $n$ acaba en 0 uso la fórmula recursiva para  $n/10$, y si acaba en algo distinto uso la observación y trabajo con $n^*$. De este modo en cada paso trabajo con números de menos dígitos, por lo que acabó en a lo más $\log_{10}n $ pasos.