# Combinatorial meaning of the functional equation for logarithm

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?

-
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. – Sinai Robins Nov 16 '12 at 14:22
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. – darij grinberg Dec 30 '15 at 16:25
Oh, great, it remains to become equivalent to Peter Scholze in other things. – Fedor Petrov Dec 30 '15 at 16:35

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$.

-