¿Por qué funciona este algoritmo de combinatoria?

Question

Este algoritmo trabaja sobre una tabla de n elija k valores para cada k. Por ejemplo, para n = 4 la tabla se ve como

a
b
c               k = 1
d
---
min(a,b)
min(a,c)
min(a,d)        k = 2
min(b,c)
min(b,d)
min(c,d)
---
min(a,b,c)
min(a,b,d)      k = 3
min(a,c,d)
min(b,c,d)
---
min(a,b,c,d)    k = 4

Todo está escrito en orden lexicográfico

Ahora necesito obtener respuestas para $a,b,c,d$ . Para obtener mi respuesta para digamos 'a', tomo cada combinación que contiene 'a' y las sumo como tal:

$ M('a') = \left[ {\begin{array}{c} min(a,b) + min(a,c) + min(a,d) - (min(a,b,c) + min(a,b,d) + min(a,c,d) - (min(a,b,c,d))) \\ min(a,b,c) + min(a,b,d) + min(a,c,d) - 2 * min(a,b,c,d) \\ min(a,b,c,d) \\ \end{array} } \right] $

Esto es para la fila uno, tomando la suma de todos los minutos que contienen 'a' donde k = 1, restando esa suma de la suma de todos los minutos que contienen 'a' donde k = 3 que a su vez se resta del último valor k = 4.

Para la fila dos se toma la suma de todas las minas que contienen 'a' donde k = 3 se resta de la capa k = 4 dos veces. Y la fila tres se deja sola.

Esta ecuación equivale en realidad a ordenar $min(a,b), min(a,c), min(a,d)$ en orden descendente, y funciona para cualquier n y cualquier letra para la que se requiera una respuesta, por ejemplo, si $b < c < d < a$ ,

$M('a') = \left[ {\begin{array}{c} d \\ c \\ b \end{array} } \right]$

¿Puede alguien ayudar a explicar por qué este algoritmo termina simplemente ordenando los valores que contienen "a" en la segunda capa en orden descendente?

Answer 1

Supongamos wlog que todos los números son enteros positivos. Identificar un número $x$ con el conjunto $S(x) = \{1,\ldots,x\}$ . Tenemos $x = |S(x)|$ y $S(\min(x,y,\ldots)) = S(x) \cap S(y) \cap \cdots$ . Su fórmula se parece sospechosamente al principio de inclusión-exclusión. Mi opinión es que esta correspondencia puede ayudarte a entender el algoritmo.