Are there any nice counting arguments that identify the sum

$$S_{n,k} = {n \choose k} - {n \choose k-1} + {n \choose k-2} + \cdots + (-1)^k {n \choose 0}$$

with a simpler, more conceptually-appealing expression?

This expression comes up as the type of rank of a homology group of a somewhat complicated object and I'm hopeful I might be inspired by a counting argument.

  • $\begingroup$ $S_{n,0}=1$ doesn't it? $\endgroup$ – JMoravitz Oct 10 '18 at 5:47
  • $\begingroup$ Thanks. I did not think about those properties as carefully as I should have. I'll just edit them out. $\endgroup$ – Ryan Budney Oct 10 '18 at 19:46
  • $\begingroup$ @RyanBudney Could you help me with this please? where we are using that $f,g:(X,A)\to (Y,B)$ are homotopic in math.stackexchange.com/questions/104795/…. $\endgroup$ – Nash Jul 3 at 20:16

$$S_{n,k}=\binom{n-1}k.$$ Look at the subsets of $[n]=\{1,\ldots,n\}$ of size $\le k$, and pair off $A$ with $A\cup\{n\}$ for $A\subseteq[n-1]$. The unpaired sets are the $k$-element subsets of $[n-1]$.

  • $\begingroup$ It seems to be the binomial expansion of $(1-1)^n$. $\endgroup$ – sirous Oct 10 '18 at 7:52
  • $\begingroup$ @sirous No, since it only goes part of the way. $\endgroup$ – Lord Shark the Unknown Oct 10 '18 at 17:25
  • $\begingroup$ Thanks, that makes sense. $\endgroup$ – Ryan Budney Oct 10 '18 at 20:05

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.