El número total de subarreglos

Question

Quiero contar el número de subarreglos para un vector (no combinaciones de elementos).
Ej.

 A[1,2,3]

Tiene 6 subarreglos :

{1}, {2}, {3}, {1,2}, {2,3}, {1,2,3}

Creo que para un vector de N elementos, el número total de subarreglos es N*(N+1)/2.
No puedo demostrarlo, ¿alguien puede hacerlo?

Answer 1

Construir y contar el número de subconjuntos de tamaño k, comenzando con k = 1 y terminando en k = N. Considere k como el "tamaño" de una ventana de k elementos que escanea los elementos de izquierda a derecha. La exploración se detiene cuando el elemento más a la derecha de la ventana incluye el último de N elementos.

Numere cada elemento del 1 al N y nombre cada ventana de k elementos con el número en el extremo izquierdo de la ventana. El nombre de la ventana de k elementos mantiene un conteo del número de subconjuntos de k elementos.

k = 1 (Ventana de tamaño 1)
[1] 2 3 4 5 6 7   
1 [2] 3 4 5 6 7  
...
1 2 3 4 5 6 [7]
Entonces hay 7 subconjuntos de tamaño 1. 

k = 2 (Ventana de tamaño 2)
[1 2] 3 4 5 6 7   
1 [2 3] 4 5 6 7  
...
1 2 3 4 5 [6 7] // Observa que el elemento más a la izquierda de la ventana cuenta el número de subconjuntos de k elementos 
Entonces hay 6 subconjuntos de tamaño 2 

k = N (ventana de tamaño N)
[1 2 3 4 5 6 7]
Hay 1 subconjunto de tamaño N

Por lo tanto, el número total de subconjuntos de k elementos, para algún k particular, debe corresponder a la ventana de k elementos que incluye el N-ésimo elemento (es decir, la ventana más a la derecha). El nombre de esta ventana (y por lo tanto el número total de subconjuntos de k elementos) es N-k+1.

Repite este cálculo para k = 1, k = 2, ... k = N y suma los resultados. Esto puede escribirse como una suma: $\sum_{k=1}^{N}N-k+1\ = N + (N-1) + (N-2) + ... + 3 + 2 + 1 = (N+1)(N/2)$.