0
$\begingroup$

I need to evaluate the following sum using generating functions, and then find some counting argument to prove the resulting identity using inclusion-exclusion principle. \begin{align} \sum_{k=0}^n(-1)^k{n \choose k}(n-k) \end{align} It looks like a binomial convolution so I tried using that to obtain an identity but I can't seem to get the right one.

I have found that this sum evaluates to 0 for any $n$

$\endgroup$
1
$\begingroup$

Let $$a_n=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)\;,$$

and let $$A(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!}\;;$$

as you say, it appears that $A(x)$ is the binomial convolution of a couple of exponential generating functions. One of these is apparently

$$f(x)=\sum_{n\ge 0}(-1)^n\frac{x^n}{n!}=\sum_{n\ge 0}\frac{(-x)^n}{n!}=e^{-x}\;,$$

and the other is

$$g(x)=\sum_{n\ge 0}n\frac{x^n}{n!}=\sum_{n\ge 1}\frac{x^n}{(n-1)!}=x\sum_{n\ge 0}\frac{x^n}{n!}=xe^x\;.$$

Thus,

$$A(x)=f(x)g(x)=(e^{-x})(xe^x)=x\;,$$

and it follows that $a_1=1$, and $a_n=0$ if $n\ne 1$. Using an Iverson bracket we can say that

$$\sum_{k=0}^n(-1)^k\binom{n}k(n-k)=[n=1]\;.$$

To see this as an instance of the inclusion-exclusion principle it may be helpful to write out the first few terms of the sum:

$$\binom{n}0n-\binom{n}1(n-1)+\binom{n}2(n-2)-+\ldots$$

It appears that we’re starting with a crude count of $n$; as a first improvement we’re subtracting $n-1$ for each of $n$ things, and the second correction is adding $n-2$ for each pair of things from a set of $n$. One way to get these terms is to let $H_n$ be the set of maps $h:[n]\to[n]$ such that

  • $h$ is the identity map, and
  • $h$ is a constant function.

It’s not hard to see that $H_n=\varnothing$ if $n\ne 1$, and $H_n$ contains the unique map from $\{1\}$ to $\{1\}$ if $n=1$, so $|H_n|=a_n$ for all $n\ge 0$. The term $\binom{n}0n=n$ counts the constant functions from $[n]$ to $[n]$. The first condition requires that $h(k)=k$ for each $k\in[n]$; thus, for each $k\in[n]$ there are $n-1$ constant functions that have to be thrown away, and there are $\binom{n}1$ choices for $k$, so the first correction term is $-\binom{n}1(n-1)$. Now if $k,\ell\in[n]$ and $k\ne\ell$, any constant function that maps $[n]$ to one of the $n-2$ elements of $[n]\setminus\{k,\ell\}$ violates the first condition for both $k$ and $\ell$, so it’s been thrown away twice and needs to be added back in; there are $\binom{n}2$ pairs of distinct elements of $[n]$, so the second correction term is $\binom{n}2(n-2)$. And so on. I’ll leave it to you to clean this up and express it properly as an inclusion-exclusion argument in whatever form you’re most familiar with.

$\endgroup$

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.