No answers from stackexchange, so I'll try this here:

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

Occasionally someone asks on stackexchange 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$. (And of course $\tanh(x+y)=(\tanh x)\,\diamondsuit\,(\tanh y)$, and there's also an application to something more like ordinary trigonometric functions.)


  • 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 parenthetical remark about $\tanh$ came from the comments below the original posting. For completeness: where I said there's an application to something more like ordinary trigonometric functions, I had in mind this: Draw a line through $(0,y)$ and $(-1,0)$ and denote by $(\operatorname{cs}(y),\operatorname{ss}(y))$ its intersection with the unit circle centered at $(0,0)$. These stand for "stereographic cosine" and "stereographic sine". Then $\operatorname{cs}(y)=(1-y^2)/(1+y^2)$ and $\operatorname{cs}(y_1 y_2)=\operatorname{cs}(y_1)\,\diamondsuit\,\operatorname{cs}(y_2)$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jun 26 '14 at 21:56
  • $\begingroup$ . . . this is conjugate to the thing with $\tanh$, but you have to use an exponential function for that, whereas $\operatorname{cs}$ is a rational function. $\endgroup$ – Michael Hardy Jun 26 '14 at 21:57

The algebraic significance of the operation $\diamond$ is that $(a+b)/(1+ab)$ is a formal group law. See Enumerative Combinatorics, vol. 1, 2nd ed., Exercise 1.163. As for $a_1\diamond\cdots\diamond a_n$, when $n\to \infty$ we get the symmetric function $(e_1+e_3+e_5+\cdots)/(1+e_2+e_4+\cdots)$. Writing this as a power series $e_1+(e_3-e_2e_1)+\cdots$, the terms of even degree are 0, and the term of degree $2n+1$ is (up to sign) the skew Schur function $s_{\tau_n}$, where $\tau_n$ is the "staircase border strip" of Enumerative Combinatorics, vol. 2, Exercise 7.64. There is a lot of interesting combinatorics, started by Foulkes, connected with this symmetric function. See also http://math.mit.edu/~rstan/papers/altenum.pdf.

  • $\begingroup$ Thank you, Richard! I'll have to look at how to get that power series. The alternation between $\diamondsuit$ and $\clubsuit$ that I mentioned actually occurs in trigonometric identities. $\endgroup$ – Michael Hardy Jun 29 '14 at 19:13

Your Answer

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

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