# How do I count the subsets of a set whose number of elements is divisible by 3? 4?

Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that

$\displaystyle \sum_{k=0}^{n} {n \choose k} = (1 + 1)^n$

while

$\displaystyle \sum_{k=0}^{n} (-1)^k {n \choose k} = (1 - 1)^n$.

It follows that

$\displaystyle \sum_{k=0}^{n/2} {n \choose 2k} = 2^{n-1}$.

A direct combinatorial proof is as follows: fix an element $s \in S$. If a given subset has $s$ in it, add it in; otherwise, take it out. This defines a bijection between the number of subsets with an even number of elements and the number of subsets with an odd number of elements.

The analogous formulas for the subsets with a number of elements divisible by $3$ or $4$ are more complicated, and divide into cases depending on the residue of $n \bmod 6$ and $n \bmod 8$, respectively. The algebraic derivations of these formulas are as follows (with $\omega$ a primitive third root of unity): observe that

$\displaystyle \sum_{k=0}^{n} \omega^k {n \choose k} = (1 + \omega)^n = (-\omega^2)^n$

while

$\displaystyle \sum_{k=0}^{n} \omega^{2k} {n \choose k} = (1 + \omega^2)^n = (-\omega)^n$

and that $1 + \omega^k + \omega^{2k} = 0$ if $k$ is not divisible by $3$ and equals $3$ otherwise. (This is a special case of the discrete Fourier transform.) It follows that

$\displaystyle \sum_{k=0}^{n/3} {n \choose 3k} = \frac{2^n + (-\omega)^n + (-\omega)^{2n}}{3}.$

$-\omega$ and $-\omega^2$ are sixth roots of unity, so this formula splits into six cases (or maybe three). Similar observations about fourth roots of unity show that

$\displaystyle \sum_{k=0}^{n/4} {n \choose 4k} = \frac{2^n + (1+i)^n + (1-i)^n}{4}$

where $1+i = \sqrt{2} e^{ \frac{\pi i}{4} }$ is a scalar multiple of an eighth root of unity, so this formula splits into eight cases (or maybe four).

Question: Does anyone know a direct combinatorial proof of these identities?

## 3 Answers

There's a very pretty combinatorial proof of the general identity $$\sum_{k \geq 0} \binom{n}{rk} = \frac{1}{r} \sum_{j=0}^{r-1} (1+\omega^j)^n,$$ for $$\omega$$ a primitive $$r$$th root of unity, in Benjamin, Chen, and Kindred, "Sums of Evenly Spaced Binomial Coefficients," Mathematics Magazine 83 (5), pp. 370-373, December 2010.

They show that both sides count the number of closed $$n$$-walks on $$C_r$$ beginning at vertex 0, where $$C_r$$ is the directed cycle on $$r$$ elements with the addition of a loop at each vertex, and a walk is closed if it ends where it starts.

Left-hand side: In order for an $$n$$-walk to be closed, it has to take $$kr$$ forward moves and $$n-kr$$ stationary moves for some $$k$$.

Right-hand side: The number of closed walks starting at vertex $$j$$ is the same regardless of the choice of $$j$$, and so it suffices to prove that the total number of closed $$n$$-walks on $$C_r$$ is $$\sum_{j=0}^{r-1} (1+\omega^j)^n.$$ For each $$n$$-walk with initial vertex $$j$$, assign each forward step a weight of $$\omega^j$$ and each stationary step a weight of $$1$$. Define the weight of an $$n$$-walk itself to be the product of the weights of the steps in the walk. Thus the sum of the weights of all $$n$$-walks starting at $$j$$ is $$(1+\omega^j)^n$$, and $$\sum_{j=0}^{r-1} (1+\omega^j)^n$$ gives the total weight of all $$n$$-walks on $$C_r$$. The open $$n$$-walks can then be partitioned into orbits such that the sum of the weights of the walks in each orbit is $$0$$. Thus the open $$n$$-walks contribute a total of $$0$$ to the sum $$\sum_{j=0}^{r-1} (1+\omega^j)^n$$. Since a closed $$n$$-walk has weight $$1$$, $$\sum_{j=0}^{r-1} (1+\omega^j)^n$$ must therefore give the number of closed $$n$$-walks on $$C_r$$.

They then make a slight modification of the argument above to give a combinatorial proof of $$\sum_{k \geq 0} \binom{n}{a+rk} = \frac{1}{r} \sum_{j=0}^{r-1} \omega^{-ja}(1+\omega^j)^n,$$ where $$0 \leq a < r$$.

Benjamin and Scott, in "Third and Fourth Binomial Coefficients" (Fibonacci Quarterly, 49 (2), pp. 99-101, May 2011) give different combinatorial arguments for the specific cases you're asking about, $$\sum_{k \geq 0} \binom{n}{3k}$$ and $$\sum_{k \geq 0} \binom{n}{4k}$$. I prefer the more general argument above, though, so I'll just leave this one as a link and not summarize it.

Fix two elements s1,s2∈S and divide subsets of S into two parts (subsets of S containing only s2)∪(subsets of S which contains s1 if they contain s2). The second part contains equal number of sets for all reminders mod 3 (because Z/3 acts there adding s1, then s2, then removing both of them) -- namely, 2n-2. And for the first part we have a bijection with subsets (edit: with 2 mod 3 elements) of a set with (n-2) elements.

So we get a recurrence relation that gives an answer 2n-2+2n-4+... -- i.e. (2n-1):3 for even and (2n-2):3 for odd n.

Errata. For n=0,1,5 mod 6 one should add "+1" to the answer from the previous paragraph (e.g. for n=6 the correct answer is 1+20+1=22 and not 21).

Let me try to rephrase the solution to make it obvious. For n=2k divide S on k pairs and consider an action of a group Z/3Z on each pair described in a first paragraph. We get an action of (Z/3Z)k on subsets of S, and after removal of it's only fixed point (k-element set consisting of second points from each pair) we get a bijection between subsets which have 0, 1 or 2 elements mod 3. So there are (2n-1):3 sets with i mod 3 elements excluding the fixed point and to count that point one should add "+1" for i=k mod 3.

And for n=2k+1 there are 2 fixed points — including or not (2k+1)-th element of S — with k+1 and k elements respectively.

• Thanks! That's easier than I thought it would be. I'll accept this answer, but if you get ideas about the 4 case I'd certainly still be interested in hearing them. Commented Jul 29, 2010 at 7:41
• I'll certainly try to think about "4 case". And looks like in "3 case" there is more than meets an eye: in the solution we identify subsets of S (|S|=2k) with P^1(Z/3)^k and consider an action of (Z/3)^k on it; and the only fixed point of the action gives "-1" in the formula. Probably I should think more about this situation. Thanks for the question! Commented Jul 29, 2010 at 11:55
• cf. artofproblemsolving.com/Forum/… (link via @Qiaochu Yuan's comment to another question) Commented Aug 25, 2010 at 17:45
• ah, thanks. I have to admit I never checked either of those solutions... Commented Aug 25, 2010 at 19:42

I try to add details with simple calculation:

for example, I show $\binom{n}{1}+\binom{n}{3}+\binom{n}{6}+\cdots=\frac{1}{3}[2^n+2\cos(\frac{n\pi}{3})]$

we know $(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n$, so if in this identity we put $1,\alpha,\alpha^2$ where $\alpha=\cos\frac{2\pi}{3}+i\sin(\frac{2\pi}{3})$respectively, then we get $$2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots$$, $$(1+\alpha)^n=\binom{n}{0}+\binom{n}{1}\alpha+\binom{n}{2}\alpha^2+\binom{n}{3}\alpha^3+\cdots$$,

$$(1+\alpha^2)^n=\binom{n}{0}+\binom{n}{1}\alpha^2+\binom{n}{2}\alpha^4+\binom{n}{3}\alpha^6+\cdots$$

but if $3\nmid n$, then we can easily see that $1+\alpha^k+\alpha^{2k}=3$ hence

$2^n+(1+\alpha)^n+(1+\alpha^2)^n=3\{\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\cdots\}$ but since $1+\alpha+\alpha^{2}=0$ hence

$1+\alpha=-\alpha^2=\cos(\frac{\pi}{3})+i\sin(\frac{\pi}{3})$ and also $1+\alpha^2=-\alpha=\cos(\frac{\pi}{3})-i\sin(\frac{\pi}{3})$ hence $$2^n+(1+\alpha)^n+(1+\alpha^2)^n=2^n+2\cos(\frac{n\pi}{3})$$, so we get the desired result.