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

Supongamos que tu vector es $\langle a_1,a_2,\ldots,a_n\rangle$. Imagina un elemento virtual $a_{n+1}$ al final; no importa cuál sea su valor. Un subarreglo está completamente determinado por el índice de su primer elemento y el índice del elemento que inmediatamente sigue a su último elemento. Por ejemplo, el subarreglo $\langle a_3,\ldots,a_{n-2}\rangle$ está determinado por los índices $3$ y $n-1$, el subarreglo $\langle a_k\rangle$ está determinado por los índices $k$ y $k+1$, y el subarreglo $\langle a_2,\ldots,a_n\rangle$ está determinado por los índices $2$ y $n+1$. Además, cada par de índices distintos del conjunto $\{1,2,\ldots,n+1\}$ determina de manera única un subarreglo. Por lo tanto, el número de subarreglos es el número de pares de índices distintos del conjunto $\{1,2,\ldots,n+1\}$, que es

$$\binom{n+1}2=\frac{n(n+1)}2\;.$$

Agregado el 21 de enero de 2024: Al abordar este problema por primera vez, uno podría llegar a la idea de identificar un subarreglo por las ubicaciones de sus primeros y últimos elementos. Hay $\binom{n}2$ pares de ubicaciones, por lo que hay $\binom{n}2$ subarreglos cuyos primeros y últimos elementos no son iguales, es decir, $\binom{n}2$ subarreglos de longitud mayor a $1$. Claramente hay $n$ subarreglos de longitud $1$, y un poco de álgebra produce el resultado deseado; este es el enfoque adoptado en un par de comentarios a continuación y en la respuesta de KRoy.

Añadí el elemento virtual $a_{n+1}$ para usar la misma idea básica sin tener que dividir los subarreglos en dos casos. Cada subarreglo de $\langle a_1,a_2,\ldots,a_{n-1}\rangle$ se puede identificar por su primer elemento y el elemento que sigue inmediatamente a su último elemento. Por supuesto, los subarreglos que terminan con $a_n$ no pueden identificarse de esta manera, porque no hay un próximo elemento después de $a_n$. Por lo tanto, simplemente fingimos que hay un elemento $a_{n+1}$ inmediatamente después de $a_n$, y entonces cada subarreglo de $\langle a_1,a_2,\ldots,a_n\rangle$ corresponde a un par único de posiciones en el vector extendido $\langle a_1,\ldots,a_n,a_{n+1}\}$, y viceversa.

Si, por ejemplo, $n=8$, los subarreglos $\langle a_3,a_4,a_5\rangle$ y $\langle a_7\rangle$ están identificados por los pares $\{3,6\}$ y $\{7,8\}$, respectivamente. Un subarreglo como $\langle a_7,a_8\rangle$ con último elemento $a_8$ no puede identificarse de esta manera, sin embargo, ya que el vector original tiene solo ocho elementos. Pero si añadimos un elemento virtual $a_9$, podemos identificar el subarreglo $\langle a_7,a_8\rangle$ por el par $\{a_7,a_9\}$.

Answer 2

Este cálculo se puede ver como una serie aritmética (es decir, la suma de los términos de una secuencia aritmética).

Suponiendo la secuencia de entrada: $(a_0, a_1, \ldots, a_n)$, podemos contar todos los subarreglos de la siguiente manera:

$ \begin{align} \; 1 & \; \text{subarreglo desde} \; a_0 \; \text{hasta} \; a_{n-1}\\ + \; 1 &\; \text{subarreglo desde} \; a_1 \; \text{hasta} \; a_{n-1}\\ & \; \ldots \\ + \; 1 & \; \text{subarreglo desde} \; a_{n-1}\; \text{hasta} \; a_{n-1}\\ = & \; n \end{align} $

$+$

$ \begin{align} \; 1 & \; \text{subarreglo desde} \; a_0 \; \text{hasta} \; a_{n-2}\\ + \; 1 &\; \text{subarreglo desde} \; a_1 \; \text{hasta} \; a_{n-2}\\ & \; \ldots \\ + \; 1 & \; \text{subarreglo desde} \; a_{n-2}\; \text{hasta} \; a_{n-2}\\ = & \; n-1\\ \end{align} $

$+ \; \ldots$

$ \begin{align} \; \; \; 1 & \; \text{subarreglo que solo contiene a} \; a_0\\ = & \; 1\\ \end{align} $

lo que resulta en la serie aritmética: $n + n-1 + … + 1$.

Lo anterior también se puede representar como $\sum_{i=1}^{n}i\;$ y suma a $n (n+1)/2$.

Answer 3

Considere un arreglo arbitrario de N ELEMENTOS DISTINTOS (¡si los elementos son iguales, entonces temo que la fórmula que intentas probar ya no funciona!).

Naturalmente existe 1 arreglo que consiste en todos los elementos (indexados de 0 a N-1)

Existen 2 arreglos que consisten en N-1 elementos consecutivos (indexados de 0 a N-2)

y en general existen k arreglos que consisten en N-k+1 elementos consecutivos (indexados de 0 a N-k-1)

Prueba:

Podemos acceder a los elementos 0 ... N-k-1 como el primer arreglo, luego 1 ... N-k+2 es el segundo arreglo, y así sucesivamente para todos N-k+r hasta que N-k+r = N-1 (es decir, hasta que hayamos alcanzado el final). El valor de r que nos da esto se puede resolver como:

$$ N-k+r = N-1 \rightarrow r -k = -1 \rightarrow r = k-1 $$

Y la lista $$0 ... k-1$$ contiene k elementos en su interior

Por lo tanto, notamos que el conteo total de subarreglos es

1 para N elementos

2 para N-1 elementos

3 para N-2 elementos

.

.

.

N para 1 elemento

Y la suma total debe ser:

$$ 1 + 2 + 3 ... N$$

Veamos si tu fórmula funciona

si:

$$ 1 + 2 +3 ... N = \frac{1}{2}N(N+1)$$

entonces

$$ 1 + 2 + 3 ... N+1 = \frac{1}{2}(N+1)(N+2)$$

Verificamos:

$$ \frac{1}{2}N(N+1) + N+1 = (N+1)(\frac{1}{2}N + 1) = (N+1)\frac{N+2}{2} $$

¡Así que tu fórmula realmente funciona! Ahora verificamos eso para N = 1

$$ \frac{1*(1+1)}{2} = 1 $$

Y por lo tanto podemos usar la lógica anterior para demostrar que para cualquier y TODOS los números enteros N ¡la fórmula funciona!

Answer 4

Profundizando en la respuesta de Brian, vamos a asumir que contamos todas las subcadenas de un solo carácter. Puede haber n de esas subcadenas de un solo carácter. Utilizando el Coeficiente Binomial, notación $\binom{n}{r}$, podemos decir que n = $\binom{n}{1}$.

$$ total_1 = n = \binom{n}{1}$$

Ahora vamos a asumir que contamos todas las subcadenas que no son de un solo carácter. Debido a que tenemos que elegir el principio y el final de la subcadena sin importar el orden, el conteo debería ser $\binom{n}{2}$.

$$total_* = \binom{n}{2}$$

Ahora el número total de subcadenas,

$$total = total_1 + total_* = \binom{n}{1} + \binom{n}{2}$$

Ahora recordemos el triángulo de Pascal y la relación de recurrencia $$\binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1}$$. Entonces podemos escribir,

$$total = total_1 + total_* = \binom{n}{1} + \binom{n}{2} = \binom{n+1}{2} = n(n+1)/2$$

Allí tenemos la deducción matemática. (Siento que no necesitamos la elegante relación de recurrencia para obtener la respuesta final, sin embargo).

Answer 5

Tratando de explicar en términos sencillos.

Vamos a decir f(0) = 0

f(1) = 1
f(2) = 3
f(3) = 6
f(4) = 10
f(5) = 15   

Por observación, puedes ver que cada resultado es simplemente una adición del resultado anterior y el número actual.

f(n) = n + f(n-1)

Entonces, con esta fórmula vamos a expandir f(5).

f(5) 
=> 5 + f(4) 
=> 5 + 4 + f(3) 
=> 5 + 4 + 3 + f(2) 
=> 5 + 4 + 3 + 2 + f(1) 
=> 5 + 4 + 3 + 2 + 1 + f(0)
=> 5 + 4 + 3 + 2 + 1 + 0 
===> Esto es igual a la suma de n números = n(n+1)/2