Eliminación de números mayores que X

Question

Si tienes un rango de números del 1 al 49 con 6 números para elegir, de los casi 14 millones de combinaciones posibles, ¿cuántas combinaciones quedan si eliminas todas las combinaciones que contienen un valor especificado "mayor que" para cada uno de los 6 números? Ejemplo:

a1 = 11

a2 = 20

a3 = 28

a4 = 35

a5 = 42

a6 = 49

"a1", 13, 22, 25, 31, 42 (Cualquier combinación en la que el valor del primer número sea mayor que "a1" se elimina de los 14 millones de combinaciones. Digamos que se han eliminado 2 millones de combinaciones, ahora sólo quedan 12 millones de combinaciones)

11, "a2", 22, 25, 31, 42 (De nuevo, cualquier combinación en la que el valor del segundo número sea mayor que "a2" también se eliminará de los 12 millones de combinaciones restantes. Digamos que se eliminan otros 2 millones de combinaciones, ahora sólo quedan 10 millones)

Repite hasta a6.

Eliminando todas las combinaciones mayores que a1 hasta a6 de los 14 millones de combinaciones, ¿cuántas combinaciones quedan?

Answer 1

Se puede calcular mediante una recursión. Sea $f(n,k)$ sea el número de opciones permitidas de la primera $n$ números si el $n$ es igual a $k$ . Usted tiene

• $f(n,k)=f(n,k-1)+f(n-1,k-1)$ cuando $k \le a_k$
• $f(n,k)=0$ cuando $k \gt a_k$
• $f(n,0)=0$ cuando $n \gt 0$
• $f(0,k)=0$ cuando $k \gt 0$
• $f(0,0)=1$

Entonces querrá $\sum\limits_{k=0}^{49} f(6,k)$

Con $(a_1,a_2,a_3,a_4,a_5,a_6)=(49,49,49,49,49,49)$ se obtiene $13983816$ para la suma final

Con $(a_1,a_2,a_3,a_4,a_5,a_6)=(11,20,28,35,42,49)$ se obtiene $7458913$ para la suma final