If we set $\exp(x)=\sum x^k/k!$, then $\exp(x+y)=\exp(x)\cdot \exp(y)$. In terms of coefficients it means that $(x+y)^n=\sum \frac{n!}{k!(n-k)!} x^ky^{n-k}$, i.e. just binomial expansion.

Now consider logarithm. Set $L(x):=\sum_{k>0} x^k/k$, then $L(x)=-\log(1-x)$ in a sense, and hence $$L(u+v-uv)=L(u)+L(v),$$ i.e. $\sum (u+v-uv)^n/n=\sum (u^n+v^n)/n$, or, if we pass to coefficients of $u^av^b$ ($a,b\geq 1$), we get $$ \sum_k (-1)^k\frac{(a+b-k-1)!}{(a-k)!(b-k)!k!}=0 $$

The question is what is combinatorial meaning of this identity. Maybe, it is some exclusion-inclusion formula, as it is usual for alternating sums?

  • 1
    $\begingroup$ Nice question - the Lagrange inversion formula (Chapter 5 of Stanley's book Enumerative Combinatorics, Vol. 2) might help here, giving the cofficients of the Log in terms of certain derivatives of the coefficients of its inverse, the exponential. $\endgroup$ – Sinai Robins Nov 16 '12 at 14:22
  • $\begingroup$ This is equivalent to Peter Scholze's question at artofproblemsolving.com/community/c6h16482p288334 (except that he uses the letters $i $ and $j $ instead of $a $ and $b$, assumes $i\geq j $ in order to be able to leave out the zero addends, and reindexes the sum by substituting $k $ for $i+j-k $). The proof I gave in post #6 appears to be essentially the same as David Speyer's. $\endgroup$ – darij grinberg Dec 30 '15 at 16:25
  • 4
    $\begingroup$ Oh, great, it remains to become equivalent to Peter Scholze in other things. $\endgroup$ – Fedor Petrov Dec 30 '15 at 16:35
  • $\begingroup$ See also math.stackexchange.com/questions/3021631/…. $\endgroup$ – Ira Gessel May 19 '19 at 17:47

As David noted, since the summands aren't in general integers, it's difficult to give a combinatorial interpretation to the formula. However, if we multiply by $a$ or $b$ we get integers and we can give a combinatorial interpretation to the identity that we obtain (though doing this destroys the symmetry between $a$ and $b$).

If we multiply by $b$, the sum may be written $$\sum_{k=0}^a (-1)^k \binom{a+b-k-1}{a-k}\binom{b}{k}.$$ This is a special case ($m=a+b-1$) of the more general identity $$\sum_{k=0}^a (-1)^k\binom{m-k}{a-k}\binom{b}{k} = \binom{m-b}{a},$$ which we can prove combinatorially. (Incidentally, this identity is a form of Vandermonde's theorem.)

To prove this formula, we start with a set $M$ of size $m$, with a subset $B$ of size $b$. To interpret $\binom{m-k}{a-k}\binom{b}{k}$, we choose a $k$-subset $K$ of $B$ and then choose an $(a-k)$-subset $C$ of $M-K$. The right side $\binom{m-b}{a}$ counts pairs $(K,C)$ in which $K$ is empty and $C$ is an $a$-subset of $M-B$. To prove the identity, we find an involution on the set of pairs $(K,C)$ not of this form that changes the parity of $|K|$. The pairs $(K,C)$ to be canceled are those in which $K\cup C$ contains at least one element of $B$. Then the involution moves the smallest element of $(K\cup C) \cap B$ from $K$ to $C$ or from $C$ to $K$.


I don't know a combinatorial interpretation, but here is a quick proof. Let $1 \leq a \leq b$. Write $$\sum_{0 \leq k \leq a} (-1)^k \frac{(a+b-k-1)!}{(a-k)! (b-k)! k!} = \frac{1}{a!} \sum_{0 \leq k \leq a} (-1)^k \frac{(a+b-k-1)!}{(b-k)!} \binom{a}{k}$$ $$= \frac{1}{a!} \sum_{0 \leq k \leq a} (-1)^k f(k) \binom{a}{k}$$ where $$f(k) = (a-1+b-k)(a-2+b-k) \cdots (2+b-k)(1+b-k).$$ Since $f(k)$ is a polynomial of degree $a-1$, its $a$-th difference is zero. (We used the assumption $0 \leq k \leq a \leq b$ to make sure that $(a+b-k-1)! / (b-k)!$ is never $0/0$.)

A combinatorial interpretation may be difficult because the summands are not always integers. EG: $a=b=2$ gives $3/2 - 2+1/2=0$.


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.