Contar el número de "subconjuntos especiales"

Question

Dejemos que $A(n)$ - es el conjunto de números naturales $\{1,2, \dots ,n\}$ .

Dejemos que $B$ - es cualquier subconjunto de $A(n)$ . Y $S(B)$ es la suma de todos los elementos $B$ .

Subconjunto $B$ es un "subconjunto especial" si $S(B)$ divisible por $2n$ ( Mod $[S(B),2n]=0$ ).

Ejemplo: $A(3)=\{ 1,2,3 \}$ así que sólo tenemos dos "subconjuntos especiales" $\{\varnothing\}$ y $\{1,2,3\}$ .

$A(5)=\{ 1,2,3,4,5 \}$ , por lo que tenemos $4$ "subconjunto especial" - $\{\varnothing\}, \{1,4,5\}, \{2,3,5\}, \{1,2,3,4\}$ .

Dejemos que $F(n)$ es el número de todos los "subconjuntos especiales" para $A(n)$ , $n \in \mathbf{N}$ .

He encontrado para $n<50$ que $F(n)-1$ es el número entero más cercano a $\frac{2^{n-1}}{n}$ . $F(n)$ =Suelo $[\frac{2^{n-1}}{n} + \frac{1}{2}] + 1$ .

¿Es posible demostrar esta fórmula para cualquier $n$ -?

Answer 1

Dejemos que $B_j$ sean variables aleatorias Bernoulli independientes con parámetro $1/2$ es decir, toman valores $0$ y $1$ , cada una de ellas con una probabilidad $1/2$ y $X = \sum_{j=1}^n j B_j$ . Así, $X$ es la suma de un subconjunto de $A(n)$ . Su $F(n) = 2^n P(X \equiv 0 \mod 2n) = \frac{2^n}{2n} \sum_{\omega} E[\omega^X]$ donde la suma es sobre el $2n$ Las raíces de la unidad ( $\omega = e^{\pi i k/n}, k=0,1,\ldots, 2n-1$ ). Ahora $$E[\omega^X] = \prod_{j=1}^n E[\omega^{j B_j}] = \prod_{j=1}^n \frac{1 + \omega^j}{2} $$ Para $\omega = 1$ tenemos $E[1^X] = 1$ , así que esto nos da un término $2^{n-1}/n$ . Cada $\omega \ne 1$ es una primitiva $m$ La raíz de $1$ es decir $\omega = e^{2\pi i k/m}$ donde $m$ divide $2n$ y $\gcd(k,m)=1$ . Ahora $E[\omega^X] = 0$ si algunos $\omega^j = -1$ . Esto es cierto si $m$ es par. Cada primitiva $m$ 'th raíz para el mismo $m$ da el mismo valor para $E[\omega^X]$ (aparecen los mismos factores, sólo que en distinto orden). Me parece (viendo los primeros casos) que si $\omega$ es una primitiva $m$ 'th raíz con $m$ impar, $E[\omega^X] = 2^{-n+n/m}$ . Ahora hay $\phi(m)$ primitivo $m$ 'th raíces, por lo que tengo $$ F(n) = \frac{2^{n-1}}{n} + \sum_m \frac{\phi(m)}{n} 2^{n/m-1} $$ donde la suma es sobre todos los divisores Impares de $n$ excepto $1$ .

No es cierto que $F(n) -1$ es el número entero más cercano a $2^{n-1}/n$ aunque $2^{n-1}/n$ es el mayor término de $F(n)$ . Por ejemplo, $F(25) = 671092$ pero $2^{25-1}/25 = 671088.64$ .