La creación de un summatory lista sin iteración

Question

Vamos a la lista de $S_k$ ser arbitraria lista de números (no necesariamente puede ser ordenado).

Lista de $S_{k+1}$ es creado a través de la suma acumulativa de los elementos de la lista $S_k$.

Por ejemplo, si $S_k$ = [2,5,7,9], a continuación, $S_{k+1}$ = [2,7,14,23]

Hay una manera de saber qué números estará en la lista de $S_n$ $n>k$ sin la necesidad de crear todos los intermedios de las listas?

Answer 1

El uso de $S_k(i)$ a indicar el $i^{th}$ plazo de $S_k$, luego

$$S_n(j) = \sum_{i \le j} {n-k-1+j-i \choose j-i} S_k(i)$$ así que usted sólo necesita hacer sumas ponderadas sobre la secuencia original.

Answer 2

Se obtiene la siguiente lista de multiplicación de la izquierda con una triangular inferior de la matriz $L$ todos $1$'s.

$$ L = \begin{pmatrix} 1 & 0 & \dotsc & 0 \\ \vdots & \ddots & \ddots & \vdots \\ \vdots & & \ddots & 0 \\ 1 & \dotsc & \dotsc & 1 \end{pmatrix} $$

A continuación, puede encontrar rápidamente la secuencia de $n$ mediante el cálculo de $L^n$ que se puede hacer con bastante rapidez, e.g por el cuadrado y multiplicar método.

Answer 3

Esta es una respuesta a la solicitud de comentarios a mostrar cómo llegar a la fórmula para las entradas de $L^h$

Aquí está un ejemplo de cómo podemos encontrar las entradas de $L^h$ simbólicamente. Yo lo hago con el $4 \times 4 $ triangular de la matriz de $L$ $$ M(h) = \exp( h \cdot \log (L)) = L^h $$ y obtener por $M$ $$ M(h) = \left[ \begin{array} {rrrr} 1 & . & . & . \\ 1h & 1 & . & . \\ \frac 12( 1 h^2+ 1 h) & 1h & 1 & . \\ \frac 16( 1h^3+ 3 h^2+ 2 h) & \frac 12 (1h^2+ 1h) & 1h & 1 \end{array} \right]$$ Aquí un ojo entrenado reconoce los números de Stirling de 1ª clase como los coeficientes de las potencias de $h$ y debido a que la estructura de la matriz tiene esta constante de las diagonales es fácil hacer la fórmula para la transferencia: $$ M(h)\cdot S_k = S_{k+h} $$ Un paso más se muestra, que la evaluación de los polinomios en las entradas conduce a la binomial números, que es un conocido de la propiedad de los números de Stirling de primera especie (la vandermonde de la matriz de LDU-se descompone en las matrices de Stirling-los números 2º clase y de los coeficientes binomiales y por lo tanto reduce por la multiplicación de la matriz de los números de Stirling 1'st tipo (que es la inversa de la 2ª clase de la matriz) para binomios)

---

Me he divertido para continuar un poco. Factorización de la smbolic entradas, suponiendo que el hypothese que tenemos siempre los números de Stirling de 1ª clase y la fracción de cofactores de la recíproca fatorials dar
$$ M(h) = \left[ \begin{array} {llll} 1 & . & . & . \\ 1(h) & 1 & . & . \\ \frac 12( h(h+1)) & 1(h) & 1 & . \\ \frac 16( h(h+1)(h+2)) & \frac 12 ( h(h+1)) & 1(h) & 1 \end{array} \right]$$ y esto da inmediatamente los coeficientes binomiales $$ M(h) = \left[ \begin{array} {cccc} 1 & . & . & . \\ \binom{h}{1} & 1 & . & . \\ \binom{h+1}{2} & \binom{h}{1} & 1 & . \\ \binom{h+2}{3} & \binom{h+1}{2} & \binom{h}{1} & 1 \end{array} \right]$$

and a routine could solve the problem given the vector S of dimension n in the following way:

   T = 0*S ;  \\ initialize an empty array of size of S
   b  = 1;    \\ contains the current binomial   
   for(j=1,n,
       for(k=j,n, T[k]+=S[k+1-j]*b);
       b *= (h+j-1)/j;
       );
   return(T);

So we have $n^2/2$ operaciones por el bucle.