This is a follow-up to this question: show that if $n$ is a positive integer then $$\sum_{k=1}^{n}\frac{(-1)^{k+1}}{k}\binom{n}{k} =\sum_{k=1}^{n}\frac{1}{k}\ .$$ I was able to answer the question by an argument involving definite integrals, but I would be interested to see a combinatorial proof. There is a proof here by induction, which however IMHO is not a true combinatorial proof as it does not rely on solving a counting problem in two ways.

In a comment on my answer, Jack D'Aurizio pointed to the problem of counting the number of cycles in a permutation. Picking up on this hint we may try the following.

We write all $n!$ permutations of $\{1,\ldots,n\}$ as products of disjoint cycles and count the total number of cycles, including repetitions. Any particular cycle $(x_1\ \ldots\ x_k)$ occurs once for every permutation of $\{1,\ldots,n\}-\{x_1,\ldots,x_k\}$; that is, it occurs $(n-k)!$ times. There are $P(n,k)/k$ cycles of length $k$, so the answer to the question is $$\sum_{k=1}^n \frac{P(n,k)}{k}(n-k)!=n!(RHS)\ .$$ But I am unable to show that the answer is also $n!(LHS)$. The alternating signs and binomial coefficients suggest inclusion/exclusion, but I can't make it work. On the other hand, inclusion/exclusion is normally used to avoid counting repetitions, and here I do want to count repetitions, so perhaps I'm completely on the wrong track.

Any ideas?

  • $\begingroup$ does $x(x-1)(x-2)\ldots (x-n+1) = {n \brack n} - {n \brack {n-1} + \ldots \pm {n \brack 1}$ have a inclusion-exclusion interpretation? $\endgroup$ – abel Jun 3 '14 at 12:35
  • $\begingroup$ @abel not sure but I will think about it! Thanks for the suggestion. $\endgroup$ – David Jun 4 '14 at 1:30

You may have a look at my answer of the original question which arguments combinatorically based upon permutations of $n+1$ elements with two cycles and the inclusion-exclusion principle. ... And you're right, usually we use the IEP the other way round, namely transform at least information to exactly information! :-)


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.