¿Cuántas veces se ejecuta la declaración de impresión?

Question

Hola, Me he metido mucho en este ejercicio, con la siguiente información:

Aquí es una matriz de ejemplos (de eje vertical es n=1,2,3,4,5,6,7,8; de eje horizontal es k=1,2,3,4)

1: 1  1   1   1    
2: 2  3   4   5    
3: 3  6  10  15    
4: 4 10  20  35    
5: 5 15  35  70    
6: 6 21  56 126    
7: 7 28  84 210    
8: 8 36 120 330

Ahora, hay un evidente patrón entre los números, siendo triangular números, la suma de los números triangulares, de suma de suma de números triangulares, y así sucesivamente. Mi pregunta es:

Me puedes ayudar a encontrar la forma cerrada de expresiones para las sumas de las entradas:

1. Abajo las columnas
2. A través de las filas
3. Y para general n,k?

Gracias!

Answer 1

El patrón que se observa Triangular, números, sumas, etc.) se puede encontrar en el triángulo de Pascal:

Un poco de razonamiento, junto con el conocimiento de que el $k$th elemento en la $n$th fila del triángulo de Pascal es $\binom{n}{k}$ te debería conducir a una solución por el patrón de búsqueda. La lógica detrás de la solución es la siguiente:

Para encontrar mi solución, pensé en el problema como una lista de $k$ niveles, donde puede comenzar en cualquier número de $1$ $n$y reducir el número de cada momento. Es útil pensar en añadir un nivel extra en cualquiera de los lados, de modo que los dos lados son fijos. Agregar un $n$ al principio, dado que no puede comenzar más que eso, y agregar un $1$ al final, ya que no puede terminar más que eso. A continuación, puede representar una instrucción print como una cadena de $i_1-i_2-i_3\ldots i_{k-1}-i_k$. En cada nuevo nivel de bucle, que puede o no puede disminuir su número. Entonces usted puede hacer (para n=3,k=3) $(3)-3-3-3-(1)$ o $(3)-3-2-1-(1)$. A continuación, puede utilizar las estrellas y las barras (1) (2), con $n$ 'estrellas' (movimientos hacia abajo) y $k$ 'barras' (divisores; los números o guiones entre los saltos). Por lo tanto, usted consigue $\binom{k+n-1}{k}$ instrucciones de impresión.

Por ejemplo, el siguiente código python se ejecuta para el caso de $n=5,k=3$:

>>> x=0
>>> n=5
>>> for i_1 in range(1,n+1):
...   for i_2 in range(1,i_1+1):
...     for i_3 in range(1,i_2+1):
...       x+=1
...       print n,"-",i_1,"-",i_2,"-",i_3,"-",1
... 
5 - 1 - 1 - 1 - 1
5 - 2 - 1 - 1 - 1
5 - 2 - 2 - 1 - 1
5 - 2 - 2 - 2 - 1
5 - 3 - 1 - 1 - 1
5 - 3 - 2 - 1 - 1
5 - 3 - 2 - 2 - 1
5 - 3 - 3 - 1 - 1
5 - 3 - 3 - 2 - 1
5 - 3 - 3 - 3 - 1
5 - 4 - 1 - 1 - 1
5 - 4 - 2 - 1 - 1
5 - 4 - 2 - 2 - 1
5 - 4 - 3 - 1 - 1
5 - 4 - 3 - 2 - 1
5 - 4 - 3 - 3 - 1
5 - 4 - 4 - 1 - 1
5 - 4 - 4 - 2 - 1
5 - 4 - 4 - 3 - 1
5 - 4 - 4 - 4 - 1
5 - 5 - 1 - 1 - 1
5 - 5 - 2 - 1 - 1
5 - 5 - 2 - 2 - 1
5 - 5 - 3 - 1 - 1
5 - 5 - 3 - 2 - 1
5 - 5 - 3 - 3 - 1
5 - 5 - 4 - 1 - 1
5 - 5 - 4 - 2 - 1
5 - 5 - 4 - 3 - 1
5 - 5 - 4 - 4 - 1
5 - 5 - 5 - 1 - 1
5 - 5 - 5 - 2 - 1
5 - 5 - 5 - 3 - 1
5 - 5 - 5 - 4 - 1
5 - 5 - 5 - 5 - 1
>>> x
35

$35=\binom{5+3-1}{3}=\binom{7}{3}$

Answer 2

SUGERENCIA: Prueba la inducción. El código dentro del bucle$i$ th se repite$n - i + 1$ veces.

Answer 3

Este es un estándar de "estrellas y barras" problema.

Por $n\geq1$ $k\geq1$ tenemos para contar el número de $k$-tuplas $(i_1,\ldots,i_k)$ tal que $$1\leq i_k\leq i_{k-1}\leq\ldots\leq i_2\leq i_1\leq n\ .$$ Cada uno de esos $k$-tupla puede ser codificado como un $0$-$1$-secuencia de longitud $n+k-1$ como sigue: Comenzar por escrito $n-1$, o barras de $|$, dejando suficiente espacio entre ellos. Estas barras de crear $n$ espacios entre ellos y en los extremos. Los espacios que representan los números $1$, $2$, $\ldots$, $n$. Para cada una de las $i_j$ escribimos un $0$ en el espacio correspondiente a su valor, lo que hace un total de $k$ ceros. A la inversa: Dada una $0$-$1$-secuencia con exactamente $n-1$ queridos y $k$ ceros que de inmediato se puede leer la secuencia de $(i_1,\ldots,i_k)$, de forma codificada.

Hay $${n+k-1\choose k}$$ tales secuencias, y este es también el número de veces que el comando de impresión se ejecuta en el citado programa.