I just had to make use of an elementary rational function identity (below). The proof is a straightforward exercise, but that isn't the point. First, "my" identity is almost surely not original, but I don't have a reference for it. Perhaps someone knows it (like a lost cat without a collar) or, more likely, could spot this as a special case of a more general identity. Second, the obvious proof is not much of an explanation: a combinatorial identity often arises for a conceptual reason, and I'd be happy to hear if anyone sees mathematics behind this one.

Let $f(x_1,\ldots,x_n)=\prod_{p=1}^n\big(\sum_{i=p}^n x_i\big)^{-1}$. Then $$ f(x_1,\ldots,x_n)+f(x_2,x_1,x_3,\ldots,x_n)+\cdots+f(x_2,\ldots,x_n,x_1)=\big(\sum_{i=1}^n x_i\big)/x_1\cdot f(x_1,\ldots,x_n), $$ where $x_1$ appears as the $i$th argument to $f$ in the $i$th summand on the left side, for $1\leq i\leq n$. But why?


I have seen a cat of a similar breed in the representation theory of symmetric groups. Out of habit, let me quote a lemma attributed to Littlewood in

Donald Knutson, $\lambda$-rings and the Representation Theory of the Symmetric Group, Springer 1973 (LNM #308), Chapter III, section 2, p. 149:

$\sum\limits_{\sigma\in S_n} f\left(x_{\sigma\left(1\right)},x_{\sigma\left(2\right)},...,x_{\sigma\left(n\right)}\right) = \frac{1}{x_1x_2...x_n}$.

At the moment, neither does this cat imply yours, nor the other way round. But can we cross them?

Let me try. The left paw side of your cat is $\sum\limits_{\sigma\in \mathrm{Sh}\left(1,n-1\right)} f\left(x_{\sigma^{-1}\left(1\right)},x_{\sigma^{-1}\left(2\right)},...,x_{\sigma^{-1}\left(n\right)}\right)$, where $\mathrm{Sh}\left(a,b\right)$ is defined as the subgroup

$\left\lbrace \sigma \in S_{a+b} \mid \sigma\left(1\right) < \sigma\left(2\right) < ... < \sigma\left(a\right) \text{ and } \sigma\left(a+1\right) < \sigma\left(a+2\right) < ... < \sigma\left(a+b\right) \right\rbrace$

of the symmetric group $S_{a+b}$. (The elements of this subgroup $\mathrm{Sh}\left(a,b\right)$ are known as $\left(a,b\right)$-shuffles.) Now I suspect tat

$\sum\limits_{\sigma\in \mathrm{Sh}\left(a,b\right)} f\left(x_{\sigma^{-1}\left(1\right)},x_{\sigma^{-1}\left(2\right)},...,x_{\sigma^{-1}\left(a+b\right)}\right) = f\left(x_1,x_2,...,x_a\right) f\left(x_{a+1},x_{a+2},...,x_{a+b}\right)$

for any $a$ and $b$ and any $x_i$.

This generalizes your cat. Does it generalize Littlewood's? Yes, at least if we generalize it even further, to the so-called $\left(a_1,a_2,...,a_k\right)$-multishuffles (which are permutations $\sigma\in S_{a_1+a_2+...+a_k}$ increasing on each of the intervals $\left[a_i+1,a_{i+1}\right]$, where $a_0=0$ and $a_{k+1}=n$). This is not much of a generalization, since it follows from the $\left(a,b\right)$-shuffle version by induction over $k$, but applying it to $\left(1,1,...,1\right)$-multishuffles (which are simply all the elements of $S_n$) yields Littlewood's cat.

Now I see that Littlewood's cat even follows from yours, if we notice that every permutation $\sigma\in S_n$ can be written uniquely as a product $t_1t_2...t_{n-1}$, where each of the $t_k$ moves the $k$ some places to the right. (This is one of the stupid sorting algorithms.)

Oh, and I don't have a proof of my cat, but it can catch mice, so it's a good cat, isn't it?

  • $\begingroup$ I enjoy the cat comparisons. They will get a fifth vote from my voting account. (If the moderators let me, I would add 6 more to it.) Gerhard "Yes, I'm A Cat Person" Paseman, 2011.08.31 $\endgroup$ – Gerhard Paseman Aug 31 '11 at 16:20
  • 1
    $\begingroup$ Yes, that's an excellent cat!! So Darij conjectures that, more generally, $f$ satisfies this "shuffle-coproduct" identity for any $(a,b)$. (Which, Frédéric points out, makes $f$ into a "symmetral mould", if I understand correctly, but I'm kind of fuzzy about operads.) Is it perhaps possible to prove this using, say, some clever trick like Tom proposed for the $(1,n-1)$ case? $\endgroup$ – Graham Denham Aug 31 '11 at 19:17
  • 1
    $\begingroup$ Actually this cat is no longer a conjecture, because the proof is completely straightforward: Every $\sigma \in \mathrm{Sh}\left(a,b\right)$ satisfies either $\sigma^{-1}\left(1\right)=1$ or $\sigma^{-1}\left(1\right)=a+1$. Thus, the sum splits into two parts, each of which can be handled by induction (once for $\left(a-1,b\right)$ instead of $\left(a,b\right)$, and once for $\left(a,b-1\right)$ instead of $\left(a,b\right)$). $\endgroup$ – darij grinberg Aug 31 '11 at 22:32
  • 2
    $\begingroup$ Like every proof related to shuffles, this proof is very simple but nigh impossible to formalize. We really need a reasonable shuffle calculus. Maybe dendriform dialgebras can be of use here. $\endgroup$ – darij grinberg Aug 31 '11 at 22:34
  • 1
    $\begingroup$ For me, they come from the shuffle Hopf algebra. ;) $\endgroup$ – darij grinberg Sep 1 '11 at 7:32

This property ( or rather the generalized version by Darij using (a,b)-shuffles ) means that f is what is called a "symmetral mould" in the context of Ecalle's theory of moulds. There is a related notion of "alternal mould" where the right hand side is 0 rather than a product of two f.

Here is just one reference among many : page 591 of

Jean Ecalle; Bruno Vallet The arborification-coarborification transform: analytic, combinatorial, and algebraic aspects

This may not be transparent when looking at this article. Maybe page 2 of my article

The anticyclic operad of moulds

would be more clear, but it only defines "alternal moulds".


  • The symmetral property is really a property of sequence of functions $f_n$, with $f_n$ a function of $n$ variables $x_1,\dots,x_n$.

  • The notions of alternal and symmetral moulds, when considered under some specific point of view, turn into the notion of primitive and group-like element in a Hopf algebra.


I'm not sure whether my answer is conceptual in your sense, but here is a relatively short proof. First of all, your definition of $f$ suggests the notation $$s_p := \sum_{i=p}^n x_i.$$ Now consider the following telescopic sum: \begin{equation}\label{eq} (1 - z_2) + z_2(1 - z_3) + z_2 z_3 (1 - z_4) + \dotsm + z_2 \dotsm z_{n-1} (1 - z_n) + z_2 \dotsm z_n = 1. \quad (*) \end{equation} For each $i \in \{2,\dots,n\}$, take $$z_i = \frac{s_i}{x_1 + s_i},$$ hence $$1 - z_i = \frac{x_1}{x_1 + s_i},$$ and plug this into the telescopic sum $(*)$. Divide both sides of the equation by $x_1 \cdot s_2 s_3 \dotsm s_n$ to get the desired expression.

  • 2
    $\begingroup$ That's nicer than my argument (namely: just rewrite in terms of $s_i$'s, clear denominators, and collapse). It's possible, I guess, that my identity can only be seen as an obscured form of (*), in which case I should not expect too much from it. But I'll remain optimistic for a while. $\endgroup$ – Graham Denham Aug 31 '11 at 14:26
  • $\begingroup$ You say the definition of f suggests the notation s_i = ..., but s_i makes no sense: the i on the right side is the index of summation. You meant s_p, not s_i. $\endgroup$ – KConrad Sep 2 '11 at 12:50
  • $\begingroup$ @KConrad: Sorry for the obvious typo; I will correct it. Thanks for noticing :) $\endgroup$ – Tom De Medts Sep 3 '11 at 17:31

A simple proof of the Sh(a,b) cat, using iterated integrals, is as follows. Note that $$ f(x_1,\ldots,x_n)=\int_{1>t_1>\cdots>t_n>0} dt_1\cdots dt_n \ t_1^{x_1-1}\cdots t_n^{x_n-1}\ . $$ Littlewood's identity follows from changing variables using the permutation so as to keep the integrand fixed. Then one has a sum of simplices (corresponding to all possible relative orderings of the variables) which recombines into a cube of integration $[0,1]^n$. The proof of the Sh(a,b) identity follows the same idea. Here the total volume of integration is a product of simplices which is broken into a union of simplices. This is probably well known to people working with moulds, operads, etc.

An additional remark: Littlewood's identity follows from Lemma II.2 in my article "Trees forests and jungles: a botanical garden for cluster expansions" with V. Rivasseau. To see this, extract the coefficient of the highest degree monomial in the v variables (notations of that article), then specialize the u variables to the case where $u_{i, i+1}=x_i$ and all other pair variables are zero (killing all edges of the complete graph which are not in a `spanning chain'). The Lemma in our article is related to many other topics in mathematical physics such as the Wilson-Polchinski renormalization group equation, see e.g. these slides.

  • $\begingroup$ So Graham was right, it was a stray cat from the land of topology. (Incidentally, Damien Calaque answered another question of mine about shuffles using your integral: mathoverflow.net/questions/63923/… .) $\endgroup$ – darij grinberg Sep 1 '11 at 19:35
  • $\begingroup$ I think the cat is too feral to belong to one particular land... $\endgroup$ – Abdelmalek Abdesselam Sep 1 '11 at 19:40
  • $\begingroup$ A geometric argument! That's very nice too. $\endgroup$ – Graham Denham Sep 3 '11 at 14:03

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.