¿Cuál es el número de disposición de N personas de diferentes alturas de modo que a lo sumo K de ellas sean visibles desde el frente de la línea? …

Answer 1

Supongamos que se nos dan las alturas en orden ordenado. Queremos calcular f (N, K) = número de formas de ordenar a las N personas de modo que exactamente K sea visible desde el frente.

• Defina cnt [i] como el número de personas con alturas menores o iguales a la persona i. Si todas las alturas hubieran sido distintas, habríamos tenido cnt [i] = i para todo i.
• Defina g (i, j) = número de formas de ordenar a las personas numeradas i … N de modo que exactamente j sean visibles desde el frente. Obviamente, g (1, K) = f (N, K).

Tratemos de calcular g (i, k).

Tenemos la opción de colocar a cualquiera de las personas i … N como la primera persona en la fila. Supongamos que elegimos a la persona j. Tenga en cuenta que cualquier persona con una altura menor o igual a la de la persona j no será visible independientemente de dónde se coloquen. Esto sería cnt [j] – j people. Además, su ubicación no afecta la visibilidad de nadie más de ninguna manera. Esto significa que podemos colocar y permutar a las personas cnt [j] – j de la forma que quieran. De las personas restantes, necesitamos poder ver personas K-1. Esto nos da la recurrencia.

g (i, k) = suma de ((Ni) P (cnt [j] -i)) g (cnt [j] + 1, k-1) de j = i a N

Si todas las alturas hubieran sido diferentes, habríamos tenido:

g (i, k) = suma de ((Ni) P (ji)) g (j + 1, k-1) de j = i a N

Los casos base de la recurrencia son g (N + 1,0) = 1, g (N + 1, k) = 0 para k> 0.

Answer 2

Supongo que su pregunta requiere que N personas (sin que haya dos personas que tengan la misma altura) se paren una detrás de la otra de tal manera que, como máximo, se ve a K personas desde el frente. Deje que denote a las personas como 1, 2, 3, …, N en orden ascendente de altura, de modo que N sea el más alto y 1 el más bajo.

Consideremos ahora el caso en el que las personas son visibles. Dondequiera que esté la enésima persona, ciertamente es visible. Además, todos los que están detrás de él no son visibles. Si j personas se encuentran frente a él, el problema es el mismo en el que tenemos que encontrar el número de arreglos de j personas donde i-1 son visibles.

Entonces, si [math] f_ {i} (N) [/ math] es la disposición de N personas de modo que soy visible, [math] f_ {i} (N) = (N-1)! \ sum \ limits _ {j = i-1} ^ {N-1} \ frac {f_ {i-1} (j)} {j!} [/ math] con [math] f_ {1} (N) = (N-1)! [/ Matemáticas]. Esta recursividad se puede resolver en una computadora y luego se calcula la suma [matemática] \ suma \ límites _ {k = 1} ^ {K} f_ {k} (N) [/ matemática].
Analíticamente, [matemáticas] f_ {i} (N) = (N-1)! \ sum \ limits _ {p_1 = i-1} ^ {N-1} \ frac {1} {p_1} \ sum \ limits _ {p_2 = i-2} ^ {p_1-1} \ frac {1} { p_2} [/ matemáticas]…. [matemáticas] \ sum \ limits _ {p_ {i-1} = 1} ^ {p_ {i-2} -1} \ frac {1} {p_ {i-1}} [/ matemáticas] para i> 1.