Demostrar que hay $[e ~(b-1) ~(b-1)!]$ números naturales sin dígitos repetidos en base $b$

Question

Por ejemplo, en la base $2$ tenemos exactamente $2$ de ellos (sin contar el cero):

$$1,~10$$

En la base $3$ tenemos $10$ (si estoy en lo cierto):

$$1,2,10,12,20,21,102,120,201,210$$

Por la observación de estos casos simples veo que la cantidad de tales números es:

$$N_b=(b-1)+(b-1)^2+(b-1)^2(b-2)+(b-1)^2(b-2)(b-3)+\dots+ \\ +(b-1)^2(b-2)\cdots(b-(b-1))$$

Así que tenemos:

$$N_4=48$$

$$N_5=260$$

$$N_{10}=8877690$$

¿Es correcta esta fórmula? ¿Tiene una forma cerrada (o una más conveniente al menos)?

Editar

Encontré la secuencia aquí: http://oeis.org/A036918

La fórmula es:

$$N_b=[e ~(b-1) ~(b-1)!]$$

¿Cómo demostrarlo?

Answer 1

Para un $m$ -tupla de base distinta- $b$ dígitos, $1 \le m \le b$ Hay $\dfrac{b!}{(b-m)!}$ posibilidades. Para una serie de $m$ dígitos, con el $0$ no está permitido, hay $$a_m = \dfrac{b-1}{b} \dfrac{b!}{(b-m)!}$$ En total tenemos $$ \sum_{m=1}^b a_m = \dfrac{b-1}{b} \sum_{j=0}^{b-1} \dfrac{b!}{j!} = (b-1)\sum_{j=0}^{b-1} \dfrac{(b-1)!}{j!}$$ Para mayor comodidad, escriba $b-1 = c$ . $$c!\; e = \sum_{j=0}^\infty \dfrac{c!}{j!}$$ Los términos para $j \le c$ son números enteros, mientras que para $j > c$ tenemos $$ \sum_{j=c+1}^\infty \dfrac{c!}{j!} < \sum_{k=1}^\infty \dfrac{1}{(c+1)^{k}} = \dfrac{1}{c} $$ Así, $$ c \sum_{j=0}^c \dfrac{c!}{j!} < c! \; c e < 1 + c \sum_{j=0}^c \dfrac{c!}{j!} $$ es decir $$\lfloor c!\; ce \rfloor = c \sum_{j=0}^c \dfrac{c!}{j!} = \sum_{m=1}^b a_m$$

Answer 2

Podemos determinarlo directamente escribiendo el número de . En particular, el número de cadenas de números distintos en $\{0,1,\ldots,b-1\}$ de longitud $n$ sin comenzar con $0$ se ve fácilmente como $$\frac{b-1}b\cdot \frac{b!}{(b-n)!}$$ que, expandido, es lo mismo que has escrito. Si sumamos esto, obtenemos $$N_k=\frac{b-1}b\sum_{n=1}^{b}\frac{b!}{(b-n)!}=(b-1)\cdot (b-1)!\cdot \sum_{n=1}^b\frac{1}{(b-n)!}$$ Yendo un poco más allá, podemos reescribir la suma por sustitución dando: $$N_k=(b-1)\cdot (b-1)! \cdot \sum_{u=0}^{b-1}\frac{1}{u!}.$$ Ahora, sólo observamos que, si dejamos que $b-1$ ir al infinito, la suma sola convergería rápidamente a $e$ . En particular, considere la diferencia $$e(b-1)(b-1)!-N_k=\sum_{u=b}^{\infty}\frac{(b-1)(b-1)!}{u!}.$$ Si podemos demostrar que esta diferencia es menor que $1$ hemos terminado. Para ello, tenga en cuenta que $u!>b!\cdot b^{u-b}$ para $u>b$ . Usando este límite: $$e(b-1)(b-1)!-N_k<\sum_{u=b}^{\infty}\frac{(b-1)(b-1)!}{b!\cdot b^{u-b}} = \frac{b-1}b\cdot \sum_{v=0}^{\infty}\frac{1}{b^v}=\frac{b-1}b\cdot \frac{b}{b-1}=1$$ Así que hemos terminado.

Answer 3

Existe una fórmula de recurrencia para $N_k$ .

En primer lugar, reescribir $N_k$ como $$ N_k = (k-1)\Big[1 + (k-1) + (k-1)(k-2) + \dots + (k-1)!\Big]. $$ Ahora es fácil ver que $$ N_{k+1} = \left(\frac{N_1}{k-1}k + 1\right)k = \frac{k^2}{k-1}N_k + k. $$ Por ejemplo $N_3 = \frac{2^2}{1}N_2 + 2 = 10$ , $N_4 = \frac{3^2}{2}N_3 + 3 = 48$ .

---

Un poco más profundo

Podemos sustituir en esa relación rucurrente $N_k = \frac{(k-1)^2}{k-2}N_{k-1} + k - 1$ y obtener $$ N_{k+1} = \frac{k^2(k-1)}{k-2}N_{k-1} + k(k-1). $$ Así, $$ N_{k+1} = (1-\alpha)\left(\frac{k^2}{k-1}N_k + k\right) + \alpha\left(\frac{k^2(k-1)}{k-2}N_{k-1} + k(k-1)\right), $$ y podemos tomar $\alpha$ tal que $(1-\alpha)k + \alpha k(k-1) = 0$ es decir $\alpha = -1/k$ . Así, $$ N_{k+1} = \frac{(k+1)k}{k-1}N_k - \frac{k(k-1)}{k-2}N_{k-2}. $$

Por ejemplo $N_4 = \frac{4\cdot 3}{2}N_3 - \frac{3\cdot 2}{1} N_2 = 48$ .

Ahora dejemos que el vector $\mathbf{N}_k = (N_k, N_{k-1})^{\top}$ . Sabemos que $\mathbf{N}_2 = (2,10)^\top$ . Si denotamos la matriz $A_k$ como $$ A_k = \begin{pmatrix} \dfrac{(k+1)k}{k-1} & -\dfrac{k(k-1)}{k-2} \\ 1 & 0 \end{pmatrix} $$ entonces obtenemos $$ \mathbf{N}_{k+1} = A_k\mathbf{N}_k $$ así $$ \mathbf{N}_n = \left(\prod_{k=3}^{n}A_k\right)\mathbf{N}_2. $$