# Why does this Combinatorics Algorithm work?

This algorithm works on a table of n choose k values for each k. e.g. for n = 4 the table looks like

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


Everything is written in lexicographic ordering

Now I need to get answers for $a,b,c,d$. To get my answer for say 'a', I take each combination that contains 'a' and add them as such:

$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]$

This is for row one, taking the sum of all mins that contain 'a' where k = 1, subtracting that sum from the sum of all mins containing 'a' where k = 3 which itself it subtracted from the last k = 4 value.

For row two taking the sum of all mins containing 'a' where k = 3 subtracted from the k = 4 layer twice. And row three is left alone.

This equation actually works out to be equivalent to sorting $min(a,b), min(a,c), min(a,d)$ in descending order, and works for any n and any letter an answer is required for. e.g. if $b < c < d < a$,

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

Can someone help explain why this algorithm ends up simply sorting the values that contain 'a' in the second layer in descending order?

-
I don't fully understand your $M$ thingamajiggie (isn't it a $k=2,3,4$ in your example, not $k=1,3,4$; how does the form generalize to arbitrary $n$?) but part of the answer probably involves an argument by symmetry. I.e. assume without loss of generality that $a>b>c>d>e>\cdots$ and then work out $M(a)$, $M(b)$, and so forth explicitly. –  anon Jul 22 '11 at 9:17

Suppose wlog that all numbers are positive integers. Identify a number $x$ with the set $S(x) = \{1,\ldots,x\}$. We have $x = |S(x)|$ and $S(\min(x,y,\ldots)) = S(x) \cap S(y) \cap \cdots$. Your formula looks suspiciously like the inclusion-exclusion principle. My guess is that this correspondence can help you understand the algorithm.

-
Thanks for pointing me to the inclusion-exclusion principle, looks like I can explain it with that, as then my formula is equivalent to taking the union or maximum value per selected combinations containing 'a' per k layer. –  Projectile Fish Jul 22 '11 at 23:55