Is there a combinatorial interpretation for a sum that includes $(-1)^k$?

Question

There are a lot of combinatorial sums that one can prove with a combinatorial interpretation like double counting. For example \begin{align*} \begin{array}{c} \displaystyle{\sum_{k = 0}^n \binom{n}{k} = 2^n}\\ \text{The number of the subsets of $\{1, \ldots, n\}$} \end{array}\\ \ \\ \hline \end{align*} \begin{align*} \begin{array}{c} \displaystyle{\sum_{j = 0}^k \binom{m}{j}\binom{n}{k - j} = \binom{m + n}{k}}\\ \text{Choose $k$ balls from a bag that includes $m$ red balls and $n$ blue balls} \end{array}\\ \ \\ \hline \end{align*} \begin{align*} \begin{array}{c} \displaystyle{\sum_{k = 0}^n k\binom{n}{k}^2} = n\binom{2n-1}{n-1}\\ \text{Create a group of $n$ students with a boy as the leader from $n$ girls and $n$ boys} \end{array}\\ \ \\ \hline \end{align*} \begin{align*} \begin{array}{c} \displaystyle{\sum_\limits{k = 1}^n \frac{1}{2k - 1}\binom{2k}{k}\binom{2n - 2k}{n - k} = \binom{2n}{n}}\\ \text{The number of permutations of $n$ digits $0$ and $n$ digits $1$} \end{array}\\ \ \\ \hline \end{align*} And similar ones. But when there's a coefficient $(-1)^k$ or $(-1)^{n - k}$ in the sum, the problem is more complicated and there aren't many ideas for giving a solution. For examples \begin{align*} &\text{(A)} && \sum_{k = 0}^n (-1)^{n-k}\binom{2n}{k}^2 = \binom{2n}{n}\\ &\text{(B)} && \sum_{k = 0}^n (-1)^{n - k}\binom{n}{k}\binom{mk}{n} = m^n\\ &\text{(C)} && \sum_{k = 0}^{\lfloor n/2 \rfloor} (-1)^k \binom{n - k}{k}2^{n - 2k} = n + 1 \end{align*}

My Question

Do you know any combinatorial interpretation for sums like $\text{(A), (B), or (C)}$? I know that for simpler identities like $\sum_{k = 0}^n (-1)^k\binom{n}{k} = 0$, by considering odd and even subsets we can prove the identity, but I couldn't apply the same idea to more complicated identities. Also, I think that the Inclusion-Exclusion Principle that has an alternating sum in its formula could be used here, but how?

Any idea and combinatorial approach for the general situation or especially, for $\text{(A), (B), or (C)}$ will appreciate. Note that I don't want to use other methods like generating functions, WZ pairs, or binomial expansion. Thanks.

Answer 1

Using a sign-reversing involution is a common way to give a combinatorial proof of equations involving a summation with alternating sign. A

I can do no better than to quote this answer directly: https://math.stackexchange.com/a/3401952/499816

I'll present a proof using the "Description, Involution, Exception" technique of A. Benjamin and J. Quinn to simplify the left side. Consider counting pairs $(A, B)_k$, where each item is a size-$k$ subset of $\{1, 2, \dots, 2n\}$. Clearly for each $k$ the total number of such pairs is $\binom{2n}{k}^2$.

Our involution, then, is to take the smallest element either in both sets or neither set, and either remove it from both or add it to both respectively. It should be clear that this is an involution, and that an element and its image are always counted at different parities in our summation, and thus contribute 0 to the total sum.

So, the elements not cancelled by this involution are exactly those pairs which are disjoint and whose union is all $2n$ elements. Being disjoint means having size no more than $n$, by pigeonhole, and totaling $2n$ means having at least $n$ each. Thus this is exactly the $n$-element pairs that have no overlap, which can be counted by choosing $n$ elements for the left item (as the right item must have exactly the rest). Meanwhile, the sign is inherited from the larger summation, where it is based on the parity of $k$, here $n$. This gives us $(-1)^n\binom{2n}{n}$.

C

For this, we can also use a sign-reversing involution. Consider counting the number of ways to tile a $1\times n$ rectangle with $1\times 1$ squares, where each square can be either white or black, and with $1\times 2$ dominos, where the dominos only come in one color. If you use $k$ dominos, then there will be $n-2k$ squares, so $n-k$ tiles total. There are $\binom{n-k}k$ ways to choose the locations of the dominos, and then $2^{n-2k}$ ways to choose the colors of the squares. The parity of a tiling is determined by the parity of the number of dominos.

The sign-reversing involution is to find the first instance of either a domino, or a white square immediately followed by a black square. If the first is a domino, then you replace that domino with a white square followed by a black square, and if it is a white square followed by a black square, you replace those two squares with a domino. The only tilings are not canceled out are the ones without dominos, and without any white squares immediately followed by black squares. There are $n+1$ such exceptional tilings, namely the tilings which are $j$ black squares followed by $n-j$ white squares, for each $j\in \{0,1,\dots,n\}$.

B

For this, we use an inclusion-exclusion argument. Both sides answer the following question.

There is an $m\times n$ grid of squares. How many ways are there to shade in exactly $n$ squares of the grid so that every column has at least one shaded square?

The easy answer is $m^n$; each column gets exactly one shaded square, and there are $m$ squares in each of the $n$ columns.

To explain the alternating sum, let $U$ be the set of ways to shade in $n$ squares of the grid, without the column restriction, so $|U|=\binom{mn}{n}$. For each $i\in \{1,\dots,n\}$, let $S_i$ be the set of colorings in $U$ where the $i^{th}$ column is unshaded. We are trying to count $|S_1^c\cap S_2^c\cap \dots \cap S_n^c|$. Using the principle of inclusion-exclusion, the answer is $$ \sum_{k=0}^n(-1)^k\binom{n}{k}|S_1\cap \dots \cap S_k|, $$ provided that when $k=0$, you interpret the empty intersection as $|U|$. It should be clear that $|S_1\cap \dots \cap S_k|=\binom{m(n-k)}n$, since the $n$ shaded squares can be freely chosen from the remaining $n-k$ columns. Plugging that in above and reversing the order of summation leads to desired summation, completing the proof.