Combinatorial meaning of the functional equation for logarithm

Question

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?

Answer 1

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

Answer 2

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