How do I count the parts of a set whose variety of components is divisible by 3? 4?

Allow $S$ be a set of dimension $n$. There is a very easy means to count the variety of parts with an also variety of components. Algebraically, it originates from the reality that

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


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

It adheres to that

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

A straight combinatorial evidence is as adheres to : deal with a component $s \in S$. If an offered part has $s$ in it, add it in; or else, take it out. This specifies a bijection in between the variety of parts with an also variety of components and also the variety of parts with a weird variety of components.

The similar solutions for the parts with a variety of components divisible by $3$ or $4$ are extra difficult, and also separate right into instances relying on the deposit of $n \bmod 6$ and also $n \bmod 8$, specifically. The algebraic derivations of these solutions are as adheres to (with $\omega$ a primitive 3rd origin of unity ) : observe that

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


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

which $1 + \omega^k + \omega^{2k} = 0$ if $k$ is not divisible by $3$ and also amounts to $3$ or else. (This is a grandfather clause of the distinct Fourier change. ) It adheres to that

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

$-\omega$ and also $-\omega^2$ are 6th origins of unity, so this formula divides right into 6 instances (or possibly 3 ). Comparable monitorings concerning 4th origins 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 a 8th origin of unity, so this formula divides right into 8 instances (or possibly 4 ).

Inquiry : Does any person recognize a straight combinatorial evidence of these identifications?

2019-05-07 13:31:21
Source Share
Answers: 1

Fix 2 components s 1 , s 2 ∈ S and also divide parts of S right into 2 components (parts of S having just s 2 ) ∪ (parts of S which has s 1 if they have s 2 ). The 2nd component has equivalent variety of collections for all suggestions mod 3 (due to the fact that Z/3 acts there including s 1 , after that s 2 , after that getting rid of both of them) - - particularly, 2 n - 2 . And also for the first component we have a bijection with parts (modify : with 2 mod 3 components) of a set with (n - 2) components.

So we get a reappearance relationship that offers a solution 2 n - 2 +2 n - 4 +... - - i.e. (2 n - 1) :3 for also and also (2 n - 2) :3 for weird n.

Errata. For n = 0,1,5 mod 6 one need to add"+1" to the solution from the previous paragraph (as an example for n = 6 the proper solution is 1+20+1 = 22 and also not 21).

Allow me attempt to put in other words the remedy to make it noticeable. For n = 2k divide S on k sets and also take into consideration an activity of a team Z/3Z on each set defined in a first paragraph. We get an activity of (Z/3Z) k on parts of S, and also after elimination of it's just set factor (k - component set containing 2nd factors from each set) we get a bijection in between parts which have 0, 1 or 2 components mod 3. So there are (2 n - 1) :3 collections with i mod 3 components leaving out the set factor and also to count that factor one needs to add"+1" for i = k mod 3.

And also for n = 2k+1 there are 2 set factors -- consisting of or otherwise (2k+1) - th component of S -- with k+1 and also k components specifically.

2019-05-09 08:49:06