7
$\begingroup$

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set theory) and let $B(S) = \{2n+1-s_1, \ldots, 2n+1-s_n\}$ (permutations). In general, $A(S) \ne B(S)$, but the sums of their elements are equal.

E.g., $S = \{1,2,5\} \subset \{1, \ldots, 6\}$ has $A(S) = \{3,4,6\}$, sum 13, and $B(S) = \{2,5,6\}$, sum 13.

My question is not how to prove this (it's a nice proof appropriate for a discrete math course), rather the history of this result or at least a citation. For me, this arose in looking at applications of permutations to fair division of indivisible goods.

$\endgroup$
4
  • $\begingroup$ One should not call $B$ complement; the term "reflection" seems more appropriate. $\endgroup$
    – Marc van Leeuwen
    Mar 27, 2013 at 8:02
  • 1
    $\begingroup$ Good to hear from you, Marc. The precedent for calling $B$ complement is, e.g., Eric Egge's "Restricted Symmetric Permutations" (Ann. Combin. 11, 2007). For a permutation $\pi = (\pi_1, \ldots, \pi_n)$, he looks at the inverse, the reverse $(\pi_n, \ldots, \pi_1)$, and the complement $(n+1-\pi_1, \ldots, n+1-\pi_n)$. The $S$ in my question is a particular "half" permutation. Is reflection also in the literature? $\endgroup$
    – Brian Hopkins
    Mar 27, 2013 at 14:44
  • $\begingroup$ You emphasize history in bold and in the bounty description; are you aware that there's a tag math-history? It might be more useful in attracting the right people than some of the others. $\endgroup$
    – joriki
    Mar 29, 2013 at 19:27
  • $\begingroup$ Done. Thanks, Joriki. $\endgroup$
    – Brian Hopkins
    Mar 30, 2013 at 3:10

0

Reset to default

You must log in to answer this question.