18 votos

¿Cuántos números diferentes se pueden escrito si cada dígito símbolo se utiliza al menos 2 veces?

¿Cuántos números diferentes se pueden escrito si cada dígito símbolo se utiliza al menos 2 veces ?

Me gustaría encontrar la función de $P(n,d)$:

$P(n,d)$ donde $n$ es de la base, $d$ es dígitos; Algunos ejemplos: $n=3$ , $d=3$;

$$(000)_3$$ $$(111)_3$$ $$(222)_3$$

$P(3,3)=3$


Es fácil que nos puede generalizar para 3 números de un dígito que $P(n,3)=n$

$P(3,4)=3.\cfrac{4!}{4!}+\cfrac{3.2}{2!}.\cfrac{4!}{(2!)^2}=21$

  • $(0000)_3 , (1111)_3$ dos ejemplos para $3.\cfrac{4!}{4!}$
  • $(0011)_3 ,(1212)_3$ dos ejemplos para $\cfrac{3.2}{2!}.\cfrac{4!}{(2!)^2}$

$P(4,4)=4.\cfrac{4!}{4!}+\cfrac{4.3}{2!}\cfrac{4!}{2!.2!}=40$

  • $(0000)_4, (1111)_4$ dos ejemplos en $4.\cfrac{4!}{4!}$
  • $(0011)_4 ,(3232)_4 $ dos ejemplos en $\cfrac{4.3}{2!}\cfrac{4!}{2!.2!}$

$P(3,5)=3.\cfrac{5!}{5!}+3.2\cfrac{5!}{3!.2!}=63$

  • $(00000)_3 ,(22222)_3$ dos ejemplos en $3.\cfrac{5!}{5!}$
  • $(00110)_3 ,(02020)_3 $ dos ejemplos en $3.2\cfrac{5!}{3!.2!}$

$P(3,6)=3.\cfrac{6!}{6!}+\cfrac{3.2}{2!}\cfrac{6!}{3!.3!}+(3.2)\cfrac{6!}{2!.4!}+\cfrac{3.2.1}{3!}\cfrac{6!}{2!.2!.2!}=243$

  • $(000000)_3 , (222222)_3$ dos ejemplos en $3.\cfrac{6!}{6!}$
  • $(001101)_3 , (020220)_3$ dos ejemplos en $\cfrac{3.2}{2!}\cfrac{6!}{3!.3!}$
  • $(002200)_3 , (111122)_3$ dos ejemplos en $(3.2)\cfrac{6!}{2!.4!}$
  • $(112200)_3 , (102021)_3$ dos ejemplos en $\cfrac{3.2.1}{3!}\cfrac{6!}{2!.2!.2!}$

Gracias por la ayuda

EDIT: (2/21/2016)

Me he dado cuenta de mis errores en mi fórmulas de arriba y he corregido . Muchas gracias por las respuestas.

Durante mi investigación en $P(n,d)$ , tengo una conjetura. Por tanto, la pregunta que ha estado pasando en muy interesante los puntos. (No sé si es conocida conjetura o no? Por favor, hágamelo saber si usted oído hablar de él. Si es cierto, esto puede permitir generalizar El de Fermat Poco teorema para cualquier número positivo. )

Fermat poco teorema: $n^{p}\equiv n \pmod {p}$ donde $p$ es el primer número; $n$ es entero positivo y $\gcd(n,p)=1$.

Mi conjetura:

$$n^{d}\equiv P(n,d) \pmod {d}$$

donde $d$ $n$ son cualquier enteros positivos.

La conjetura es verdadera para el (7X7) tabla que @Markus Scheuer dio en su respuesta. Todos los valores en la tabla se han probado con éxito. Necesito su contribución para poner a prueba mis conjeturas para números grandes. No he encontrado ningún contraejemplo para refutar mi conjetura aún.

Tenga en cuenta que tengo la conjetura sin pruebas. ¿Cómo puede la conjetura de ser probada?

Me gustaría compartir algunos de mis resultados para $P(n,d)$ . Por favor, hágamelo saber si alguna falta en mi fórmulas a continuación.

$$P(n,1)=0$$

$$P(n,2)=n$$

$$P(n,3)=n$$

$$P(n,4)=n+\cfrac{n(n-1)}{2!}\cfrac{4!}{2!2!}=3n^2-2n$$

$$P(n,5)=n+\cfrac{n(n-1)}{1!}\cfrac{5!}{2!3!}=10n^2-9n$$

$$P(n,6)=n+\cfrac{n(n-1)}{2!}\cfrac{6!}{3!3!}+\cfrac{n(n-1)}{1!}\cfrac{6!}{4!2!}+\cfrac{n(n-1)(n-2)}{3!}\cfrac{6!}{2!2!2!}$$

$$P(n,6)=n+25n(n-1)+15n(n-1)(n-2)=15n^3-20n^2+6n$$

$$P(n,7)=n+\cfrac{n(n-1)}{1!}\cfrac{7!}{4!3!}+\cfrac{n(n-1)}{1!}\cfrac{7!}{2!5!}+\cfrac{n(n-1)(n-2)}{2!}\cfrac{7!}{3!2!2!}$$

$$P(n,7)=n+56n(n-1)+105n(n-1)(n-2)$$

Tenga en cuenta que las fórmulas de arriba satisfacer las $(7x7)$ (n/d) de la tabla que @Markus Scheuer dio en su respuesta.

Podemos escribir en términos más si queremos.

$$P(n,8)=n+\cfrac{n(n-1)}{1!}\cfrac{8!}{2!6!}+\cfrac{n(n-1)}{1!}\cfrac{8!}{3!5!} +\cfrac{n(n-1)}{2!}\cfrac{8!}{4!4!}+\cfrac{n(n-1)(n-2)}{2!}\cfrac{8!}{2!2!4!}+\cfrac{n(n-1)(n-2)}{2!}\cfrac{8!}{2!3!3!}+\cfrac{n(n-1)(n-2)(n-3)}{4!}\cfrac{8!}{2!2!2!2!}$$

..

..

$$P(n,d)=n+\cfrac{n(n-1)}{1!}\cfrac{d!}{2!(d-2)!}+\cfrac{n(n-1)}{1!}\cfrac{d!}{3!(d-3)!} +\cfrac{n(n-1)}{1!}\cfrac{d!}{4!(d-4)!}+.....$$


$$n^{d}\equiv P(n,d) \pmod {d}$$ Si ponemos los resultados por encima de mi conjetura , podemos obtener:

$$n^{2}\equiv n \pmod {2}$$ $$n^{3}\equiv n \pmod {3}$$ $$n^{4}\equiv 3n^2-2n \pmod {4}$$ $$n^{5}\equiv 10n^2-9n\pmod {5}\equiv -9n\pmod {5}\equiv n\pmod {5}$$ $$n^{6}\equiv 15n^3-20n^2+6n \pmod {6} \equiv 3n^3-2n^2 \pmod {6}$$ $$n^{7}\equiv n+56n(n-1)+105n(n-1)(n-2) \pmod {7}\equiv n \pmod {7}$$ $$n^{8}\equiv n^2(n-2)^2 \pmod {8}$$

EDIT: (2/22/2016)

Una observación:

$$(n+1)^{d}=\sum_{k=0}^{d}{d\choose k}\>n^k$$

$$(n+1)^{d}\equiv \sum_{k=0}^{d}{d\choose k}\>n^k \pmod {d}$$

Si $n^{d}\equiv P(n,d) \pmod {d}$ true;

$$P(n+1,d)\equiv \sum_{k=0}^{d}{d\choose k}\>P(n,k) \pmod {d}$$

Porque de ${d\choose d-1}=d$

$$P(n+1,d)\equiv P(n,d)+ \sum_{k=0}^{d-2}{d\choose k}\>P(n,k) \pmod {d}$$

Este resultado es muy similar resultado con la fórmula de recursión de @Cristiano, escribió Blatter en su respuesta.

$$P(n+1,d)=P(n,d)+\sum_{k=0}^{d-2}{d\choose k}\>P(n,k)\qquad(d\geq2)$$

EDITAR

He probado mi conjetura con números grandes.

De acuerdo a la tabla de secuencia de A231797 (muchas Gracias a @MarkusScheuer para el enlace)

Hay una salida para los grandes números de la Tabla de la n(n) para n = 0..410 . He probado de $n=d=410$

$P(410,410)$ es de 990 dígitos entero, se puede ver en la tabla que me dio en el enlace de arriba.

Me confirmó en una calculadora en línea que mi conjetura es verdadera para el número grande.

$$410^{410}\equiv 0 \pmod {410}$$

$$P(410,410)\equiv 0 \pmod {410}$$

$$410^{410}\equiv P(410,410) \pmod {410}$$

Nota: no he probado mi conjetura con números grandes para el caso de que $d \neq n$ . No sé de generación de función para el caso de $d \neq n$ como para $d=n$ como Markus Scheuer informó en su respuesta. Cualquier idea para la generación de la función de $d \neq n$?

La generación de la función de $d = n$

\begin{align*} P(n,n)=n![x^n]\left(e^x-x\right)^n\qquad\qquad n\geq 0 \end{align*}

Gracias por la ayuda y contribuciones

EDITAR (26/2/2016): he publicado una prueba para mi conjetura anterior. Usted puede encontrar a continuación como una respuesta. Por favor, siéntase libre de escribir comentarios acerca de ella.

$$n^{d}\equiv P(n,d) \pmod {d}$$

donde $d$ $n$ son cualquier enteros positivos.

Muchas gracias en especial a @ChristianBlatter y @MarkusScheuer por sus contribuciones a probarlo. Especialmente Cristiano Blatter repetición de la fórmula para $P(n,d)$ es la clave para demostrar la conjetura. Muchas gracias por compartir su idea con nosotros.

No he encontrado un enlace relacionado para que el teorema en el internet. Podría usted por favor, comparta libros de referencia o enlaces si lo sabes?

Muchas gracias por su ayuda

6voto

Markus Scheuer Puntos 16133

Aquí vamos a considerar dos ejemplos y derivar una fórmula general de ellos. Una pequeña mesa con una referencia a OEIS se ofrece al final.

[2016-02-22] Algunas fórmulas para las diagonales $P(n+m,n)$ y la generación de funciones de agregado.

[2016-02-23] Epílogo añadido.

Ejemplo de $P(4,4)$:

Con $n=4$ $d=4$ tenemos cuatro dígitos $0,1,2,3$ y cuatro posiciones para colocarlos. Los números permitidos contener uno o más dígitos colocados en cuatro posiciones o dos dígitos cada uno de ellos colocado en dos posiciones.

Consideramos \begin{array}{lccl} \text{type}&\text{nr of digits}&\text{nr type arrangements}&\text{nr placements of digits}\\ 4&\binom{4}{1}&\frac{1!}{1!}&\binom{4}{4}\\ 2,2&\binom{4}{2}&\frac{2!}{1!1!}&\binom{4}{2}\binom{2}{2}\\ \end{array}

y obtener \begin{align*} P(4,4)&=\binom{4}{1}\frac{1!}{1!}\binom{4}{4}+\binom{4}{2}\frac{2!}{2!}\binom{4}{2}\binom{2}{2}\\ &=4\cdot1\cdot1+6\cdot1\cdot6\cdot1\\ &=4+36\\ &=40 \end{align*}

Comentario:

  • Nº de dígitos: En el caso de tipo de $(2,2)$ hay $\binom{4}{2}$ maneras de seleccionar dos dígitos de $0,1,2,3$.

  • N ° de tipo de arreglos: Desde la posición de los dígitos en un número relevante hay $\frac{2!}{1!1!}$ formas de asignar dos dígitos para el tipo de $(2,2)$. Esto es más evidente cuando se mira por ejemplo, en el tipo de $(3,2,2)$, lo que significa tres apariciones de un dígito y dos ocurrencias de la segunda dígitos y dos de el tercer dígito. El número de diferentes tipos de arreglos en este caso es \begin{align*} \frac{3!}{1!2!} \end{align*}

  • Nr de las colocaciones de dígitos: Se puede colocar el primer dígito en $\binom{4}{2}$ formas en dos posiciones, dejando $\binom{2}{2}$ formas de colocar los otros dígitos en dos posiciones.

Consideremos un ejemplo más.

Ejemplo de $P(3,6)$: Aquí tenemos que considerar cuatro tipos diferentes $(6),(4,2),(3,3)$$(2,2,2)$.

Obtenemos \begin{array}{lccl} \text{type}&\text{nr of digits}&\text{nr type arrangements}&\text{nr placements of digits}\\ 6&\binom{3}{1}&\frac{1!}{1!}&\binom{6}{6}\\ 4,2&\binom{3}{2}&\frac{2!}{1!1!}&\binom{6}{4}\binom{2}{2}\\ 3,3&\binom{3}{2}&\frac{2!}{2!}&\binom{6}{3}\binom{3}{3}\\ 2,2,2&\binom{3}{3}&\frac{3!}{3!}&\binom{6}{2}\binom{4}{2}\binom{2}{2}\\ \end{array}

Tenemos \begin{align*} P(3,6)&=\binom{3}{1}\frac{1!}{1!}\binom{6}{6}+ \binom{3}{2}\frac{2!}{1!1!}\binom{6}{4}\binom{2}{2}+ \binom{3}{2}\frac{2!}{2!}\binom{6}{3}\binom{3}{3}+ \binom{3}{3}\frac{3!}{3!}\binom{6}{2}\binom{4}{2}\binom{2}{2}\\ &=3\cdot1\cdot1+3\cdot2\cdot15\cdot1+3\cdot1\cdot20\cdot1+1\cdot1\cdot15\cdot6\cdot1\\ &=3+90+60+90\\ &=243 \end{align*}

Nota: Los valores de $P(4,4)=40$ $P(3,6)=243$ también puede ser derivado de la recursividad de la fórmula indicada en la respuesta por @ChristianBlatter.

Fórmula para $P(n,d)$

De los ejemplos anteriores podemos obtener una fórmula para$P(n,d)$$n\geq 1, d\geq 2$.

\begin{align*} P(n,d)=\sum_{k=1}^{\lfloor\frac{d}{2}\rfloor}\binom{n}{k}\sum_{{r_1+r_2+\cdots+r_k=d}\atop{r_j\geq 2}} \binom{k}{r_1,\ldots, r_k}\prod_{j=1}^{k}\binom{d-\sum_{l=1}^{j-1}r_l}{r_j}\tag{1} \end{align*}

Tabla de $P(n,d)$

Usando la fórmula (1) o tal vez más eficaz el uso de la recursividad de la fórmula de @ChristianBlatter se encuentra que para valores pequeños de a $n$ $d$

\begin{array}{crrrrrr} n\backslash d&2&3&4&5&6&7\\ 1&1&1&1&1&1&1\\ 2&\color{blue}{2}&2&8&22&52&114\\ 3&3&\color{blue}{3}&21&63&243&969\\ 4&4&4&\color{blue}{40}&124&664&3196\\ 5&5&5&65&\color{blue}{205}&1405&7425\\ 6&6&6&96&306&\color{blue}{2556}&14286\\ 7&7&7&133&427&4207&\color{blue}{24409}\\ \end{array}

La diagonal (en azul), los valores de $P(n,n)$ igual a $2,3,40,205,2556,24409,\ldots$ se declaró como secuencia A231797 en OEIS. Nos encontramos allí

\begin{align*} P(n,n)=n![x^n]\left(e^x-x\right)^n\qquad\qquad n\geq 0 \end{align*}


Adición [2016-02-22]

Algunos de los aspectos más alrededor de $P(n,d)$. Empezamos con una fórmula explícita de $P(n,n)$ y el estado una conjetura para $P(n+m,n)$. A continuación ofrecemos una relación de las correspondientes funciones de generación. Creo que esta relación de funciones de generación es la clave para demostrar la conjetura.

Una Fórmula para $P(n,n)$:

El siguiente es válido \begin{align*} P(n,n)=\sum_{k=0}^n(-1)^{n-k}\frac{n!}{k!}\binom{n}{k}k^k \end{align*}

De hecho, esto se deduce fácilmente a partir de (2) desde

\begin{align*} P(n,n)&=n![x^n]\left(e^x-x\right)^n\\ &=n![x^n]\sum_{k=0}^n\binom{n}{k}e^{kx}(-x)^{n-k}\tag{2}\\ &=n!\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[x^k]e^{kx}\\ &=n!\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[x^k]\sum_{j=0}^\infty\frac{(kx)^j}{j!}\\ &=\sum_{k=0}^n(-1)^{n-k}\frac{n!}{k!}\binom{n}{k}k^k \end{align*}

Comentario:

  • En (2) nos reorganizar la suma y el uso de la regla de $[x^{n+m}]A(x)=[x^n]x^{-m}A(x)$

Conjetura de $P(n+m,n)$:

Jugando con los valores de $P(n+m,n)$ pequeña $m$ da lugar a la siguiente conjetura:

\begin{align*} P(n+m,n)=\sum_{k=m}^n(-1)^{n-k}\frac{n!}{k!}\binom{n-m}{k-m}k^{k-m}\qquad 0\leq m\leq n \end{align*}

$$ $$

Funciones de generación:

Consideramos que una exponencial de generación de función $A_n(x)$ $P(n,d)$ \begin{align*} A_n(x)=\sum_{d=0}^{\infty}P(n,d)\frac{x^d}{d!}\qquad\qquad n\geq 1 \end{align*} y proporcionar una relación funcional entre ellos.

El siguiente es válido \begin{align*} A_{n+1}(x)=(e^x-x)A_n(x)\qquad\qquad n\geq 1\tag{3} \end{align*}

Obtenemos

\begin{align*} e^xA_{n}(x)&=\left(\sum_{j=0}^{\infty}\frac{x^j}{j!}\right)\left(\sum_{d=0}^{\infty}P(n,d)\frac{x^d}{d!}\right)\\ &=\sum_{d=0}^{\infty}\left(\sum_{{k+j=d}\atop{k,j\geq 0}}\frac{P(n,k)}{k!j!}\right)x^d\\ &=\sum_{d=0}^{\infty}\left(\sum_{k=0}^d\binom{d}{k}P(n,k)\right)\frac{x^d}{d!}\\ &=\sum_{d=0}^{\infty}\left(P(n,d)+\sum_{k=0}^{d-2}\binom{d}{k}P(n,k)\right)\frac{x^d}{d!}+\sum_{d=0}^{\infty}dP(n,d-1)\frac{x^d}{d!}\tag{4}\\ &=\sum_{d=0}^\infty P(n+1,d)\frac{x^d}{d!}+x\sum_{d=1}^{\infty}P(n,d-1)\frac{x^{d-1}}{(d-1)!}\\ &=A_{n+1}(x)+xA_n(x) \end{align*}

y el reclamo de la siguiente manera.

Comentario:

  • En (4) aplicamos la recurrencia de la relación indicada por @ChristianBlatter

Conclusión: a partir De (3) obtenemos un cerrado expresión para $A_n(x)$ \begin{align*} A_n(x)=\sum_{d=0}^{\infty}P(n,d)\frac{x^d}{d!} =(e^x-x)^n\qquad\qquad n\geq 1\tag{5} \end{align*}

Nota: La conjetura y la representación general de la $P(n,d)$ sigue de (5). Esto se muestra en una respuesta por OP a continuación.


Adición [2016-02-23]

Epílogo: Algunas reflexiones abordar la relación con la generación de funciones

  • Binomial inversa par: La recurrencia de la relación proporcionada por @ChristianBlatter $$P(n+1,d)=\sum_{{k=0}\atop{k\ne 1}}^{d}\binom{d}{k}P(n,k)\qquad\qquad n\geq 1, d\geq 0$$

    es un ejemplo de una binomial inversa par. Para mostrar este tipo de relación se multiplica exponencial funciones de generación. Deje $A(x)=\sum_{n\ge0}a_{n}\frac{x^n}{n!}$$B(x)=\sum_{n\ge0}b_{n}\frac{x^n}{n!}$$B(x)=A(x)e^x$. La comparación de los coeficientes da el siguiente binomial inversa par \begin{align*} B(x)&=A(x)e^x&A(x)&=B(x)e^{-x}\\ b_n&=\sum_{k=0}^{n}\binom{n}{k}a_k&a_n&=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}b_k \end{align*} Este simple y muchos otros ejemplos de la binomial inversa pares se pueden encontrar por ejemplo, en la Combinatoria de las Identidades de un clásico de John Riordan ($1968$).

  • Generalización: La generación de la función de la relación de recurrencia es \begin{align*} A_{n+1}(x)=(e^x-x)A_n(x)\qquad\qquad n\geq 1 \end{align*} Parece ser que hay una fuerte relación entre el término $-x$ $(e^x-x)$ y el salteado índice $k=1$ en la recurrencia de la relación. Un natural generalsation podría pedir para la relación y la interpretación de \begin{align*} B_{n+1}(x)=(e^x-\sum_{k=1}^m\frac{x^k}{k!})B_n(x)\qquad\qquad m,n\geq 1 \end{align*}

  • La divisibilidad de la propiedad: La propiedad de nice $P(n,d)\equiv n^d\pmod{d}$ tiene la siguiente representación a través de la generación de la función \begin{align*}\ d\left|\left(P(n,d)-n^d\right)\right.\qquad\qquad\qquad \frac{1}{x}\left((e^x-x)^n-e^{nx}\right)\qquad\qquad n\geq 1 \end{align*} La afirmación de la divisibilidad de $P(n,d)-n^d$ $d$ es equivalente a la afirmación de que los coeficientes de las funciones de generación son parte integral. Buscando en la generación de la función por un corto periodo de tiempo y esto se hace evidente.

5voto

CodingBytes Puntos 102

Uno tiene la siguiente recursión: $$P(1,0)=1,\quad P(1,1)=0,\quad P(1,d)=1\quad(d\geq2),$$ y, a continuación, $$\eqalign{P(n+1,0)&=1,\quad P(n+1,1)=0,\cr P(n+1,d)&=P(n,d)+\sum_{k=0}^{d-2}{d\choose k}\>P(n,k)\qquad(d\geq2)\ .\cr}$$ La prueba de la recursividad de la fórmula: se obtiene la admisibilidad de una cadena de longitud $d$ sobre el alfabeto $[n+1]$ eligiendo $k\in\{0,2,3,\ldots,d\}$ células para colocar el dígito $n+1$ y luego rellenar el resto de las células con la admisibilidad de una palabra de longitud $d-k$ sobre el alfabeto $[n]$. Esto lleva a $$P(n+1,d)=\sum_{0\leq k\leq d, \ k\ne1}{d\choose k}P(n,d-k)\ ,$$ que se transforma fácilmente en la fórmula de arriba.

3voto

Marko Riedel Puntos 19255

Podemos mantener esto simple. El etiquetado de las especies de secuencias de $q$ define con al menos dos elementos está dada por

$$\mathfrak{S}_{=q}(\mathfrak{P}_{\ge 2}(\mathcal{Z})).$$

Obtenemos el total admisible de las contribuciones a $P(n,d)$ eligiendo $q$ valores de la $n$ dígitos diferentes y dejar que el primer set se la las posiciones de los más pequeños elegido dígitos, el siguiente de la segunda más pequeño y así sucesivamente. Este rendimientos de las especies

$$\sum_{q=1}^n {n\elegir q} \mathfrak{S}_{=q}(\mathfrak{P}_{\ge 2}(\mathcal{Z})).$$

Que se traduce en la generación de funciones que hemos

$$\sum_{q=1}^n {n\elegir q} (\exp(z)-1-z)^q = -1 + (\exp(z)-z)^n.$$

Esto finalmente se obtiene la fórmula cerrada

$$d! [z^d] (\exp(z)-z)^n.$$

Escribiendo esto con los números de Stirling tenemos

$$d! [z^d] (\exp(z)-1+1-z)^n = d! [z^d] \sum_{p=0}^n {n\elegir p} (\exp(z)-1)^p (1-z)^{n-p} \\ = d! \sum_{p=0}^n {n\elegir p} \sum_{q=0}^d [z^q] (\exp(z)-1)^p [z^{d-q}] (1-z)^{n-p} \\ = d! \sum_{p=0}^n {n\elegir p} \sum_{q=0}^d \frac{p!}{p!} {q\llave n} (-1)^{d-q} {n-p\elegir d-q}.$$

2voto

Priyank Puntos 159

Después de aplicar la función de la generación de la idea que @MarkusScheuer dio en su respuesta.Podemos obtener la formula de sumar de a $P(n+m,d)$

$$A_{n}(x)=\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}$$

$$A_{n+1}(x)=(e^x-x)A_{n}(x)$$

$$A_{1}(x)=(e^x-x)$$

$$A_{n}(x)=(e^x-x)^n$$

$$(e^x-x)^n=\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}$$

Podemos obtener fácilmente la relación de que la función de generación de algunas propiedades importantes.

$$(e^x-x)^n.(e^x-x)^m=(e^x-x)^{n+m}$$ $$A_{n}(x).A_{m}(x)=A_{n+m}(x)$$

$$A_{n}(x)=\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}$$

$$\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}.\sum_{d=0}^\infty P(m,d)\frac{x^d}{d!}=\sum_{d=0}^\infty P(n+m,d)\frac{x^d}{d!}$$

$$P(n+m,d)=\sum_{k=0}^d {d\choose k} P(n,d-k)P(m,k)=\sum_{k=0}^d {d\choose k} P(m,d-k)P(n,k)$$

Si seleccionamos $m=1$ , La recurrencia de la fórmula que Cristiano Blatter escribió en su respuesta puede ser obtenido.

$$P(n+1,d)=\sum_{k=0}^d {d\choose k} P(n,d-k)P(1,k)$$

$$P(1,0)=1$$ $$P(1,1)=0$$ $$P(1,j)=1$$ $$j\geq2$$ $$P(n+1,d)=P(n,d)+\sum_{k=2}^d {d\choose k} P(n,d-k)$$ $$d\geq2$$

Después de conseguir la generación de función, podemos obtener $P(n,d)$ mediante el mismo método que se muestra por Markus Scheuer en su respuesta. $$A_{n}(x)=\sum_{d=0}^\infty P(n,d)\frac{x^d}{d!}$$

$$P(n,d)=d![x^d]\left(e^x-x\right)^n$$ $$=d![x^d]\sum_{k=0}^n\binom{n}{k}e^{kx}(-x)^{n-k}$$ $$=d!\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[x^d]x^{n-k}e^{kx}$$ $$=d!\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}[x^d]\sum_{j=0}^\infty\frac{k^jx^{n-k+j}}{j!}$$ $$=\sum_{k=0}^n(-1)^{n-k}\frac{d!}{(d+k-n)!}\binom{n}{k}k^{d+k-n}$$

$$P(n,d)=n! d! \sum_{k=0}^n(-1)^{n-k}\frac{k^{d+k-n}}{(d+k-n)!(n-k)!k!}$$

o puede escribirse en orden inverso después de $m=n-k$ varible cambiar

$$P(n,d)=n! d! \sum_{m=0}^n(-1)^{m}\frac{(n-m)^{d-m}}{(d-m)!(n-m)!m!}$$

También podemos escribir :

$$P(n,d)= \sum_{k=0}^n(-1)^{k}\frac{d!}{(d-k)!}\binom{n}{k}(n-k)^{d-k} \tag{1}$$


LA PRUEBA de MI CONJETURA:

Parte 1: El caso de ($d \geq n$))

$$n^{d}\equiv P(n,d) \pmod {d}$$

Prueba: Si ampliamos la $P(n,d)$ términos de $(1)$

$$P(n,d)= n^d-dn(n-1)^{d-1}+d(d-1)\binom{n}{2}(n-2)^{d-2}-.......+(-1)^{n-1} \frac{d!}{(d-(n-1))!} \binom{n}{n-1} 1^{d-1}$$

$$P(n,d)= n^d-dn(n-1)^{d-1}+d(d-1)\binom{n}{2}(n-2)^{d-2}-.......+(-1)^{n-1} d (d-1)...(d+1-(n-1)) n$$

Como podemos ver todos los términos excepto $n^d$ $d$ y también sabemos que binom números de serie son siempre números enteros.

Así $$P(n,d) \equiv \sum_{k=0}^n(-1)^{k}\frac{d!}{(d-k)!}\binom{n}{k}(n-k)^{d-k} \pmod {d}$$

$$P(n,d) \equiv n^d \pmod {d}$$ La conjetura es demostrado para el caso de $d \geq n$ $$n^d \equiv P(n,d) \pmod {d}$$


Parte 2: El caso de ($d < n$))

$$n^{d}\equiv P(n,d) \pmod {d}$$

Prueba:

si $d<k$ $d,k$ son enteros no negativos

$$\cfrac{d!}{(d-k)!}=0 \tag{2}$$

Referencia wiki link para (2)

Si ampliamos la $P(n,d)$ términos en que caso de $(1)$

$$P(n,d)= n^d-dn(n-1)^{d-1}+d(d-1)\binom{n}{2}(n-2)^{d-2}-.......+(-1)^{n-d} d! \binom{n}{d} (n-d)^{d-d}$$

$$P(n,d)= n^d-dn(n-1)^{d-1}+d(d-1)\binom{n}{2}(n-2)^{d-2}-.......+(-1)^{n-d} d! \binom{n}{d}$$

Como podemos ver todos los términos excepto $n^d$ $d$ y también sabemos que binom números de serie son siempre números enteros.

Así $$P(n,d) \equiv \sum_{k=0}^n(-1)^{k}\frac{d!}{(d-k)!}\binom{n}{k}(n-k)^{d-k} \pmod {d}$$

$$P(n,d) \equiv n^d \pmod {d}$$

La conjetura es que también demostró para el caso de $d <n$
$$n^d \equiv P(n,d) \pmod {d}$$

La prueba se ha completado.

Muchas gracias a Blatter y Cristiano Markus Scheuer, por sus contribuciones y respuestas.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: