(The actual questions in this posting are at the bottom.)

Occasionally someone asks here how to show that every nonempty finite set has just as many subsets of odd cardinality as of even cardinality (the empty set is the unique exception). When the set has an odd number of members, a correspondence between complements does it, but generally, one picks a distinguished element. Every set containing the distinguished element corresponds to one not containing it, and that's the bijection.

Now let's take it a step further and say one adds a new element to the set, which will be "distinguished" until the next new one gets added.

$$ \begin{array}{c|c} \text{odd} & \text{even} \\ \hline a & \text{---} \\ b & ab \\ c & ac \\ abc & bc \end{array} $$ Now add the new element $d$: $$ \begin{array}{c|c} \text{odd} & \text{even} \\ \hline a & \text{---} \\ b & ab \\ c & ac \\ abc &bc \\ \hline d & ad \\ abd & bd \\ acd& cd \\ bcd& abcd \end{array} $$ Those listed on the odd side get re-listed on the even side and vice-versa, and the new element is added to both.

Suppose that as above we let multiplication denoted by juxtaposition represent a set of ur-elements, and addition represent a set of sets, so the first table above has $a+b+c+abc$ as its left column and $1+ab+ac+ad$ as its second column, the $1$ being the product of members of the empty set. If, further, we represent the whole table as a fraction with the odd column as the numerator and the even column as the denominator, then the operation of adding the new element is this: $$ \frac{\frac{a+b+c+abc}{1+ab+ac+bc}+d}{1+\frac{a+b+c+abc}{1+ab+ac+bc}d} = \frac{a+b+c+d+abc+abd+acd+bcd}{1+ab+ac+ad+bc+bd+cd+abcd}. $$ So we're working with a binary operation: $a\,\diamondsuit\, b=\dfrac{a+b}{1+ab}$. When the set we start with is empty, the the numerator is the sum of $0$ terms and is $0$ and the denominator is the product of $0$ terms and $\text{is }1$.


  • Does this algebraic way of looking at this shed light on the combinatorics, or vice-versa?
  • What is the combinatorial meaning of the fact that the binary operation is associative?
  • I tried this with the even terms in the numerator and odd in the denominator: $a\,\spadesuit\, b$. We get $(a\,\spadesuit\,b)\,\spadesuit\,c =a\,\diamondsuit\,b\,\diamondsuit\,c$; and $(a_1\,\diamondsuit\,\cdots\,\diamondsuit\,a_n)\,\spadesuit\, a_{n+1} = 1/(a_1\,\diamondsuit\,\cdots\,\diamondsuit\,a_{n+1})$ --- So if you apply the $\spadesuit$ operation instead of $\diamondsuit$ each time a new element is added, then you alternate between odd-in-the-numerator-and-even-in-the-denominator and even-in-the-numerator-and-odd-in-the-denominator. Does the alternation have some combinatorial significance?
  • $\begingroup$ The $\diamond$ operator sure looks a lot like the formula for $\tan(a\pm b)$, which makes things even more interesting. Who knows, maybe there's a geometric interpretation to all this ? $\endgroup$ – Lucian Jun 25 '14 at 4:38
  • 1
    $\begingroup$ If you write the numerator and denominator as elementary summetric polynomials, then you get e1/(1+e2) ; (e1+e3)/(1+e2) ; (e1+e3)/(1+e2+e4) ; (e1+e3+e5)/(1+e2+e4) ; ... each time adding ek to the numerator if k odd, else to the denominator. But I guess you saw that already. $\endgroup$ – Wouter M. Jun 25 '14 at 16:04
  • $\begingroup$ @Lucian : Indeed, $\tanh(x+y) = \dfrac{\tanh x+\tanh y}{1+\tanh x\tanh y}$. Moreover, there is also a geometric interpretation not involving hyperbolic functions. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jun 25 '14 at 19:16
  • 1
    $\begingroup$ Nobody's answering here, and I've tried mathoverflow: mathoverflow.net/questions/172741/… $\endgroup$ – Michael Hardy Jun 26 '14 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.