MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 (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
up vote 22 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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