Comience con una manzana en el día uno. En todos los siguientes días:
Todos los apple crece $k\cdot(c+1)$ nuevas manzanas, donde $c$ es el número de conexiones para que apple y $k$ es el número de pasos que se necesita para llega a la salida de apple desde que apple (contando el de la propia apple como un paso).
Por ejemplo, la primera apple tiene sólo un paso para sí mismo. Las manzanas de ella toma dos pasos. Las manzanas de cultivo de los tomar tres pasos, etc. (ver imágenes a continuación para más detalles)
Cuántas manzanas será en el árbol después de $n$ días?
Yo calcula primero $25$ términos: (secuencia no está en OEIS)1, 2, 8, 56, 548, 6752, 99908, 1724816, 34031348, 755384672, 18630078308, 505421692976, 14958279256148, 479591526968192, 16559455408832708, 612609633148083536, 24174100149092384948, 1013551337258199761312, 44995053102770888963108, 2108457649886329729936496, 104001928043774583748777748, 5386506619791901055945028032, 292264718383139371373233669508, 16578710198212615619201747731856, 981315128726093566691094046194548Los cuatro primeros días de este aspecto:
¿Cómo puedo encontrar una fórmula para calcular el número de manzanas en la $n$th día?
No sé cómo resolver esto, así que estoy contando las manzanas en cada capa individualmente:
La Idea era encontrar un patrón general para las capas y, a continuación, la suma de todos ellos en la final.
Nota, la Capa de $k$ tiene todas las manzanas que tome $k$ pasos para el inicio de apple.Deje que el número de capa de $k$ manzanas después de $n$ días de ser dado por $a_n(k)$.
A continuación, el número de manzanas en el árbol en el día $n$ está dado por $A_n=\sum_{i=1}^n{a_n(i)}$ .
Aquí es los datos calculados para la primera $6$ capas:
a_n(1) = 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,... a_n(2) = 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215,... a_n(3) = 0, 0, 4, 24, 100, 360, 1204, 3864, 12100, 37320, 114004, 346104, 1046500, 3155880, 9500404, 28566744, 85831300, 257756040, 773792404, 2322425784, 6969374500, 20912317800, 62745342004, 188252803224, 564791964100,... a_n(4) = 0, 0, 0, 24, 240, 1560, 8400, 40824, 186480, 818520, 3498000, 14676024, 60780720, 249401880, 1016542800, 4123173624, 16664094960, 67171367640, 270232006800, 1085570781624, 4356217681200, 17466686971800, 69992221794000, 280345359228024, 1122510953731440,... a_n(5) = 0, 0, 0, 0, 192, 2880, 26880, 201600, 1334592, 8164800, 47372160, 264844800, 1441632192, 7694406720, 40467248640, 210468585600, 1085328316992, 5559954344640, 28337142664320, 143847569376000, 727922413132992, 3674461807114560, 18512042531347200, 93120150431088000, 467843515029264192,... a_n(6) = 0, 0, 0, 0, 0, 1920, 40320, 510720, 5080320, 43827840, 344615040, 2541411840, 17896919040, 121797836160, 807731084160, 5251058991360, 33611039804160, 212519521994880, 1330716675415680, 8267671479137280, 51044504568583680, 313546251542832000, 1918022127328137600, 11693253189282297600, 71090720640004665600,...Aquí está el código de python.
Actualización
He corregido los datos de la capa; ahora me las arreglé para encontrar las fórmulas para el primer $6$ capas:
$ a_n(1)=1 $
$ a_n(2)=\frac{1}{2}(2^n-2)$
$ a_n(3)=\frac{2}{3}(3^n-3\cdot2^n+3)$
$ a_n(4)=1( 4^{n} - 4\cdot3^n + 6\cdot2^{n} - 4)$
$ a_n(5)=\frac{8}{5}(5^n - 5\cdot4^n + 10\cdot3^n - 10\cdot 2^{n}+5)$
$ a_n(6)=\frac{8}{3} (6^n - 6\cdot5^n + 15\cdot4^n - 20\cdot3^n + 15\cdot2^n - 6 )$Me di cuenta de que el patrón aquí, y observó que estas secuencias están dados por:
$$ a_n(k)=\frac{\lceil 2^{k-2} \rceil}{k} \sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i)^n$$
Y el número de manzanas en el día $n$ está así dada por:
$$ A(n)= \sum_{k=1}^n\sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i)^n\frac{\lceil 2^{k-2} \rceil}{k} $$
El hecho de que la fórmula era observable a partir de los datos es buena, pero ¿cómo ahora matemáticamente mostrar (probar) esta expresión es para todos los $n$?P: ¿Cómo se podía resolver esto (o problemas similares) algebraicamente a llegar a esta expresión? Sin depender de la computación y el patrón análisis?
Lo que si es que el creciente condición por apple se ha cambiado un poco; ¿cuáles son los métodos para resolver este y otros problemas similares?
Respuesta
¿Demasiados anuncios?
En primer lugar, debemos formalizar la definición de tener algo para trabajar. Podemos ver el problema como una secuencia de orientado a gráficos, comenzando con un solo nodo (primera manzana) y, a continuación, conectar de forma iterativa nodos adicionales. Ahora en cada día (vamos a decir $n$-ésimo día), hemos determinado número de manzanas que se $k$ pasos de distancia de la primera manzana, vamos a llamar a este número $a_{n,k}$ (hasta el momento mismo de su $a_n(k)$). Pero también tenemos cierto número entrante de los bordes de estas (las "conexiones"), vamos a llamar a este número $i_{n,k}$. Del mismo modo, hemos determinado número de bordes salientes, decir $o_{n,k}$. De esta manera hemos definido $3$ secuencias para el que es relativamente fácil encontrar la recurrencia de la relación. Más tarde, se va a simplificar estos en una sola secuencia.
Vamos a investigar estos $3$ secuencias. Puesto que no hay bordes en el primer día, tenemos $i_{1,k}=o_{1,k}=0$. También cada día tenemos $0$ entrantes bordes en $1$-st apple, y por lo $i_{n,1}=0$. También observe que en el primer día comenzamos con un solo de apple, y por lo $a_{n,1}=1$$a_{1,k}=0$$k>1$.
Ahora, dado que el número de aristas de/a los nodos $k$-pasos de distancia de crecer cada día en función de cuántos nodos y bordes estaban allí en el día anterior, y esto sucede con peso $k-1$ (lo que corresponde a su "cada manzanas crece un nuevo apple para todos los de apple conectado, incluyendo a sí mismo", por lo que tenemos $1$ contribución de borde entrante, $1$ de borde saliente y uno de cada nodo/de la propia apple). Así, por número de entrantes bordes hemos
$$ i_{n,k} = i_{n-1,k} +(k-1) (i_{n-1,k-1}+o_{n-1,k-1}+a_{n-1,k-1}). $$
Número de bordes salientes de $k$ manzanas lejos crece sólo se basa en el número de aristas y nodos que ya $k$-manzanas de lejos, con peso exactamente igual $k$, y así
$$ o_{n,k} = o_{n-1,k} +k (i_{n-1,k}+o_{n-1,k}+a_{n-1,k}). $$
Como última secuencia $a_{n,k}$ (el número real de los nodos), este crece de la misma manera como el número de la entrada de los bordes, y así
$$ a_{n,k} = a_{n-1,k}+(k-1)(i_{n-1,k-1}+o_{n-1,k-1}+a_{n-1,k-1}) $$ pero tenga en cuenta que esta secuencia no es lo mismo que $i_{n,k}$ debido a las diferentes condiciones iniciales. Ahora si denotamos $$ c_{n,k} = i_{n,k}+o_{n,k}+a_{n,k} $$ donde las condiciones iniciales $c_{n,1}=2^{n-1}$ $c_{1,k}=0$ $k>1$ puede ser verificado a partir de secuencias originales, podemos escribir un poco más compacto \begin{align} i_{n,k} &= i_{n-1,k} +(k-1) c_{n-1,k-1}\\ o_{n,k} &= o_{n-1,k} +k c_{n-1,k}\\ a_{n,k} &= a_{n-1,k} +(k-1) c_{n-1,k-1} \end{align} Podemos hacer pequeño truco para convertir las secuencias de arriba a solo dos de secuencia variable, simplemente por la suma de los $3$ ecuaciones obtenemos $$ c_{n,k}=(k+1)c_{n-1,k}+2(k-1) c_{n-1,k-1}. $$ Finalmente, dado que sólo estamos interesados en $a_{n,k}$, podemos escribir \begin{align} a_{n,k} &= a_{n-1,k} +(k-1) c_{n-1,k-1}\\ &= a_{n-2,k} +(k-1) c_{n-2,k-1}+(k-1) c_{n-1,k-1}\\ \ \ &\vdots\\ &= (k-1) c_{1,k-1}+ \dots +(k-1) c_{n-2,k-1}+(k-1) c_{n-1,k-1}\\ &= (k-1) \sum_{i=1}^{n-1}c_{i,k-1} \end{align} y de conectar la $c_{n,k}$ de la recurrencia de la relación (asumiendo $k>2$), llegamos a la \begin{align} a_{n,k} &= (k-1) \sum_{i=1}^{n-1}c_{i,k-1}\\ &= (k-1) \sum_{i=2}^{n-1}c_{i,k-1}\\ &= (k-1) \sum_{i=2}^{n-1}(kc_{i-1,k-1}+2(k-2)c_{i-1,k-2})\\ &= (k-1)k \sum_{i=2}^{n-1}c_{i-1,k-1}+2(k-1)(k-2)\sum_{i=2}^{n-1}c_{i-1,k-2}\\ &= (k-1)k \sum_{i=1}^{n-2}c_{i,k-1}+2(k-1)(k-2)\sum_{i=1}^{n-2}c_{i,k-2}\\ &= k a_{n-1,k}+2(k-1)a_{n-1,k-1} \end{align} Inicial $k=2$ caso tenemos $a_{n,2}=\sum_{i=1}^{n-1}c_{i,1} = \sum_{i=1}^{n-1}2^{i-1} = 2^{n-1}-1$. (Por la forma en que este comportamiento diferente para $k=2$ corresponde a la $\lceil 2^{k-2} \rceil$ expresión). Así que resumiendo lo que hasta ahora hemos $$ a_{n,k} = \begin{cases} 1&k=1\\ 2^{n-1}-1&k=2\\ 0 &n=1,k>2\\ ka_{n-1,k}+2(k-1)a_{n-1,k-1} &n>1, k>2 \end{casos} $$ Ahora se convierte en un problema algebraico a derivar la forma cerrada de la fórmula, o al menos demostrar que es igual a la que usted cree. Voy a hacer el último, ya que parece mucho más sencillo en este punto (y no hay nada malo acerca de averiguar el patrón de la fórmula de datos y, a continuación, probar es, además).
Así que vamos a probar que $$ a_{n,k} = a_n(k) = \frac{\lceil 2^{k-2} \rceil}{k} \sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i)^n. $$ Los casos iniciales son sencillas, por ejemplo para $k=1$: $$ a_n(1) = (-1)^0\binom{1}{0}(1-0)^n = 1. $$ Del mismo modo $$ a_n(2) = \frac{1}{2}\left[(-1)^0\binom{2}{0}(2-0)^n+(-1)^1\binom{2}{1}(2-1)^n\right] = \frac{1}{2} (2^n-2) = 2^{n-1}-1$$ y $$ a_1(k) = \frac{2^{k-2}}{k} \sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i) = 2^{k-2} \sum_{i=0}^{k-1} (-1)^i \binom{k-1}{i} = 2^{k-2}\left(1+(-1)\right)^{k-1} =0. $$ donde se utilizó $\binom{k}i (k-i)=k\binom{k-1}{i}$ y el teorema del binomio.
El último caso es demostrar que para $n>1, k>2$: $$ a_n(k) - ka_{n-1}(k)- 2(k-1)a_{n-1}(k-1) = 0. $$ Vamos a simplificar el lado izquierdo
\begin{align} LHS&=\frac{2^{k-2}}{k} \sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i)^n - k \frac{2^{k-2}}{k} \sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i)^{n-1}\\ \ \ \ &-2(k-1) \frac{2^{k-3}}{k-1} \sum_{i=0}^{k-2} (-1)^i \binom{k-1}i (k-1-i)^{n-1}\\ &=2^{k-2}\left[\frac{1}{k}\sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i)^n -\sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i)^{n-1}- \sum_{i=0}^{k-2} (-1)^i \binom{k-1}i (k-1-i)^{n-1} \right]\\ &=2^{k-2}\left[\frac{1}{k}\sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i)^n -\sum_{i=0}^{k-1} (-1)^i \binom{k}i (k-i)^{n-1}- \sum_{i=1}^{k-1} (-1)^{i-1} \binom{k-1}{i-1} (k-i)^{n-1} \right]\\ &=2^{k-2}\sum_{i=1}^{k-1}\left[(-1)^i \left( \frac{1}{k}\binom{k}i (k-i)^n - \binom{k}i (k-i)^{n-1} + \binom{k-1}{i-1} (k-i)^{n-1} \right)\right]\\ &=2^{k-2}\sum_{i=1}^{k-1}\left[(-1)^i(k-i)^{n-1} \left( \binom{k-1}{i} - \binom{k}i + \binom{k-1}{i-1} \right)\right]\\ &=0. \end{align} donde al final se utilizó $\binom{k}{i}=\binom{k-1}{i}+\binom{k-1}{i-1}$. Esto termina la prueba y verifica su fórmula es correcta.
Posiblemente hay otras maneras de acercarse a este, por ejemplo algunas de las cosas que puede ser probado de forma combinatoria en lugar de (las sumas que se parecen sospechosamente inclusión-exclusión principio), pero este es además el punto. Una vez que hemos llegado a recursiva de las relaciones (o nada preciso), podemos obtener el resultado de forma algebraica.
Esta respuesta puede sentir insatisfactorio, ya que en realidad no le llega a la fórmula, sólo hemos comprobado que es correcta, la derivación en sí es todavía "sólo" una expresión algebraica problema una vez que tenemos la recursividad y debe ser, en principio, posible. Un enfoque podría ser para formular bivariante de generación de la función de la recursividad de la fórmula que hemos encontrado.
