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$ -?

  • $\begingroup$ Have you tried cranking out a proof by induction? $\endgroup$ – Benjamin Dickman Nov 1 '12 at 1:28
  • $\begingroup$ 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). $\endgroup$ – 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$.

  • $\begingroup$ It is very difficult to me (my poor level) to understand this decision. I need some time before I'll accept it. Thank you very much! $\endgroup$ – Mike Nov 1 '12 at 5:00
  • $\begingroup$ See also oeis.org/A000016 and references there. $\endgroup$ – Robert Israel Nov 1 '12 at 7:01
  • $\begingroup$ Hmm this would explain why I was getting contradictory results to the ones posted... I thought maybe I had made an error somehow because the question poser claimed he had checked up to 50. $\endgroup$ – dinoboy Nov 1 '12 at 17:14
  • $\begingroup$ 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)$ $\endgroup$ – Robert Israel Nov 1 '12 at 19:20

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.