Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.