Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 $x^ay^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|improve this question
1  
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

2 Answers 2

up vote 14 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|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|improve this answer

Your Answer

 
discard

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.