acuerdos con todos los dígitos presentes

Question

Yo estaba pensando en sobre cerrado fórmula para el número de arreglos de elementos ("los dígitos') $1,2,\dots,n$ en una cadena de $n+r$ elementos, de tal manera que todos los dígitos están presentes al menos una vez. Por lo $r$ es el número de no-acontecimientos únicos. Si $r=0$ tenemos permutaciones, que se $n!$ en número. Si $r=1$, obtenemos $n$ opciones para reiterada de un dígito, a continuación, $n+1\choose 2$ opciones para colocar dos no únicos dígitos y, a continuación, $(n-1)!$ opciones para el resto de los únicos dígitos, que en total $n {n+1\choose 2} (n-1)!={n+1\choose 2} n!$ arreglos. Sin embargo, cuando se $r$ crece, tenemos muchas formas para repetir dígitos, correspondientes a las particiones de $r$, y las fórmulas parecer intimidante.

Otra forma de describir esta clase de acuerdos, es llamarlos permutaciones con los no especificados, de repeticiones, es decir, tenemos todos los dígitos presentes, el orden de las cosas, pero no tenemos que repetir dígitos. Las cadenas de dígitos tener estas propiedades se denominan "pandigital números' (a excepción de que ellos no le permiten a $0$ en la primera posición).

Pregunta: ¿hay una buena cerrado fórmula para el número de esta clase de arreglos?

ACTUALIZACIÓN: Usuario ", Especialmente de Lima", ha proporcionado una buena respuesta mediante la inclusión-exclusión principio (y yo acepté su respuesta). Resultó que su fórmula se simplifica a $$ n! S(n+r,n) $$ donde $S(n,m)$ es el número de Stirling del segundo tipo, la medición de la cantidad de formas de partición de una $n$-elemento establecido en $m$ no vacía de subconjuntos. Ahora es obvio cómo obtener este número desde el principio: las formas que describe las posiciones entre los lugares $1,2,\dots,n+r$ son únicos y que repita, definir una partición de la $n+r$-elemento establecido en $n$ no vacía de subconjuntos. Actuando por $n!$ permutaciones por la numeración de las etiquetas de las piezas se obtiene el resultado.

Answer 1

Creo que lo mejor que puedes hacer es la inclusión-exclusión de la fórmula. Hay $n^{n+r}$ total de secuencias. Para cada dígito $k$ hay $(n-1)^{n+r}$ secuencias que no contengan $k$, por lo que resta de los de fuera (es decir, restar $\binom n1(n-1)^{n+r}$, ya que hay $\binom n1$ opciones de $k$). Por desgracia ahora hemos restado fuera de las secuencias que no contengan $k_1$ o $k_2$ dos veces, así que tenemos que añadir los de nuevo. Continuar de esta forma obtenemos $$\sum_{a=0}^{n-1}(-1)^a\binom na(n-a)^{n+r},$$ donde el término para $a$ cuenta todas las secuencias que faltan algunas conjunto particular de $a$ dígitos, y se multiplica por el número de conjuntos de $a$ dígitos.

Answer 2

DESCARGO de responsabilidad: Este post proporciona una menor respuesta eficiente que el otro post. Lo voy a dejar aquí por si es de interés para nadie. De lo contrario, podría eliminar si sugerido.

---

Deje $f(m,n)$ denotar el número de cadenas de longitud $m\geq n$ que puede ser formado a partir de una lista de $n$ dígitos para que cada dígito se produce al menos una vez. A continuación, debemos tener $$ \binom n1f(m,1)+\binom n2f(m,2)+...+\binom n{n-1}f(m,n-1)+f(m,n)=n^m $$ y, a continuación, $$ f(m,1)=1 $$ así que $$ \begin{aligned} f(m,2)&=2^m-\binom21f(m,1)\\ &=2^m-2 \end{aligned} $$ y además $$ \begin{aligned} f(m,3)&=3^m-\binom 32f(m,2)-\binom31f(m,1)\\ &=3^m-3(2^m-2)-3 \end{aligned} $$ y así sucesivamente. No parece para obtener más bonita como $n$ crece, pero tal vez algún patrón surgirán y alguien puede ser capaz de llevar en una forma más compacta.