# Count the number of “special subsets”

Let $A(n)$ - is the set of natural numbers $\{1,2, \dots ,n\}$.

Let $B$ - is any subset of $A(n)$. And $S(B)$ is the sum of all elements $B$.

Subset $B$ is "special subset" if $S(B)$ divisible by $2n$ ( Mod$[S(B),2n]=0$).

Example: $A(3)=\{ 1,2,3 \}$, so we have only two "special subset" - $\{\varnothing\}$ and $\{1,2,3\}$.

$A(5)=\{ 1,2,3,4,5 \}$, so we have $4$ "special subset" - $\{\varnothing\}, \{1,4,5\}, \{2,3,5\}, \{1,2,3,4\}$.

Let $F(n)$ is the number of all "special subsets" for $A(n)$, $n \in \mathbf{N}$.

I found for $n<50$ that $F(n)-1$ is the nearest integer to $\frac{2^{n-1}}{n}$. $F(n)$=Floor$[\frac{2^{n-1}}{n} + \frac{1}{2}] + 1$.

Is it possible to prove this formula for any natural $n$ -?

• Have you tried cranking out a proof by induction? – Benjamin Dickman Nov 1 '12 at 1:28
• Is it a hint? Or just a suggestion? I can't imagine how it may help us to count F(k+1) if we know F(k). – Mike Nov 1 '12 at 1:51

Let $B_j$ be independent Bernoulli random variables with parameter $1/2$, i.e. they take values $0$ and $1$, each with probability $1/2$, and $X = \sum_{j=1}^n j B_j$. Thus $X$ is the sum of a randomly-chosen subset of $A(n)$. Your $F(n) = 2^n P(X \equiv 0 \mod 2n) = \frac{2^n}{2n} \sum_{\omega} E[\omega^X]$ where the sum is over the $2n$'th roots of unity ($\omega = e^{\pi i k/n}, k=0,1,\ldots, 2n-1$). Now $$E[\omega^X] = \prod_{j=1}^n E[\omega^{j B_j}] = \prod_{j=1}^n \frac{1 + \omega^j}{2}$$ For $\omega = 1$ we have $E[1^X] = 1$, so this gives us a term $2^{n-1}/n$. Each $\omega \ne 1$ is a primitive $m$'th root of $1$, i.e. $\omega = e^{2\pi i k/m}$ where $m$ divides $2n$ and $\gcd(k,m)=1$. Now $E[\omega^X] = 0$ if some $\omega^j = -1$. This is true iff $m$ is even. Each primitive $m$'th root for the same $m$ gives the same value for $E[\omega^X]$ (the same factors appear, just in different orders). It appears to me (from looking at the first few cases) that if $\omega$ is a primitive $m$'th root with $m$ odd, $E[\omega^X] = 2^{-n+n/m}$. Now there are $\phi(m)$ primitive $m$'th roots, so I get $$F(n) = \frac{2^{n-1}}{n} + \sum_m \frac{\phi(m)}{n} 2^{n/m-1}$$ where the sum is over all odd divisors of $n$ except $1$.
It's not true that $F(n) -1$ is the nearest integer to $2^{n-1}/n$, although $2^{n-1}/n$ is the largest term in $F(n)$. For example, $F(25) = 671092$ but $2^{25-1}/25 = 671088.64$.
• The equation $E[\omega^X] = 2^{-n+n/m}$ can be obtained from the identity $\sin(m\theta) = 2^{m-1} \prod_{j=0}^{m-1} \sin(\pi j/m + \theta)$ – Robert Israel Nov 1 '12 at 19:20