Encontrar el número de todos los subconjuntos de a $\{1, 2, \ldots,2015\}$ $n$ elementos tales que la suma de los elementos en el subconjunto es divisible por 5

Question

El problema es que como en la pregunta del título. Sólo una adición - $n$ no es divisible por $5$.

Ya tengo una solución que involucren permutaciones, pero recientemente leí acerca de las funciones de generación y me preguntaba si este problema puede ser resuelto con ellos.

Un problema similar es el siguiente: Encontrar el número de todos los subconjuntos de a $\{1, 2, \ldots, 2015\}$ y la suma de los elementos de cada subconjunto es divisible por 5. La generación de función que se utiliza es $${((1+x^0)(1+x^1)(1+x^2)(1+x^3)(1+x^4))}^{403}.$$

Pero esta función no se puede utilizar para mi problema, ya que tenemos que contar cuántos elementos han sido "utilizados" para hacer el subconjunto. Alguien me puede ayudar?

Answer 1

Una generación de la función solución.

Para cada $S\subset\{1,2,\ldots,2015\}$ escribiremos $\Sigma S=\sum_{k\in S}k$.

Vamos $$ f(a,x) = \prod_{k=1}^{2015} (1+un^kx) = \sum_{S\subconjunto\{1,\ldots,2015\}}^{\Sigma S} x^{|C|}. $$ Tomar el promedio de esta función a cargo de poner $5$th raíces complejas de la unidad, por $a$. Deje $\omega=e^{2\pi i/5}$; a continuación, $$ \frac15\sum_{j=0}^4 f(\omega^j,x) = \sum_{S\subconjunto\{1,\ldots,2015\}} \left(\frac15\sum_{j=0}^4 \big(\omega^{\Sigma S}\big)^j\right) x^{|C|} = \sum_{\substack{S\subconjunto\{1,\ldots,2015\}\\\Sigma S\equiv0\pmod5}} x^{|C|}. \etiqueta{$*$} $$ En el lado derecho de la $(*)$, el coeficiente de $x^n$ es el número de $n$-elemento de los conjuntos de $S\subset\{1,\ldots,2015\}$$\Sigma S\equiv0\pmod5$.

Por otro lado, $$ f(\omega^j,x)= \begin{cases} (1+x)^{2015} & \text{if } j=0 \\ (1+x^5)^{403} & \text{if } j=1,2,3,4 \end{casos} $$ así que en el lado izquierdo de $(*)$ el coeficiente de $x^n$: $\frac15\binom{2015}n$ si $n$ es co-prime con $5$, y $\frac15\binom{2015}n+\frac45\binom{403}{n/5}$ si $5|n$.

Answer 2

Esta es una aplicación directa de la Enumeración de Polya Teorema. Tratamos el problema de los subconjuntos $n$ elementos del conjunto $\{1,2,\ldots, q\}$ cuya suma es divisible por $k.$ Supongamos $Z(P_n)$ es el ciclo del índice del conjunto de operador $\mathfrak{P}_{=n}$ dada por el la repetición por Lovasz que es

$A$Z(P_n) = \frac{1}{n} \sum_{i=1}^n (-1)^{l+1} a_l Z(P_{n-l}) \quad\text{donde}\quad Z(P_0) = 1.$$

Obtenemos por la MASCOTA de la siguiente fórmula para la OGF del común de los conjuntos de

$A$Z(P_n)\left(w+w^2+\cdots+w^q\ \ derecho) = Z(P_n)\left(\sum_{m=1}^q w^m\right).$$

Con $\rho$ una raíz de la unidad, es decir, $$\rho = \exp(2\pi i/k)$$

llegamos por las que se desea contar el valor $$\frac{1}{k} \left.\sum_{p=0}^{k-1} Z(P_n)\left(\sum_{m=1}^q w^m\right)\right|_{w=\rho^p}.$$

Vamos a calcular el valor de $p=0$ por separado y para ello recordar la OGF del conjunto operador $\mathfrak{P}_{=n}$ que es

$A$Z(P_n) = [z^n] \exp\left(a_1 z - a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} - a_4 \frac{z^4}{4} +\cdots \right).$$

o

$A$Z(P_n) = [z^n] \exp\left(\sum_{i\ge 1} (-1)^{i+1} a_r \frac{z^r}{r}\right).$$

En sustitución de este en la fórmula obtenemos

$$\frac{1}{k} \sum_{p=0}^{k-1} \a la izquierda. [z^n] \exp\left(\sum_{i\ge 1} (-1)^{i+1} \frac{z^r}{r} \sum_{m=1}^q w^{rm} \right) \right|_{w=\rho^p}.$$

Al $p=0$ obtenemos $$\frac{1}{k} [z^n] \exp\left(q\sum_{i\ge 1} (-1)^{i+1} \frac{z^r}{r}\right) = \frac{1}{k} [z^n] \exp\left(q \log (1+z)\right) \\ = \frac{1}{k} [z^n] (1+z)^q = \frac{1}{k} {q\elegir n}.$$

Cambiamos a la algoritmia para el resto de esta discusión.

En el tratamiento del caso $p\ge 1$ hacemos la siguiente observación. Cuando la sustitución en los términos del ciclo de índice de los $a_r$ a partir de el producto donde $pr$ es un múltiplo de a $k$ producir el valor de $q$ mientras que el resto de $a_r$ crear una secuencia de plazo, $k$ que depende sólo en el resto $b$ al $q$ se divide por $k$ donde tomamos $1\le b\le k.$

Esto da lugar a un algoritmo que repetimos a lo largo del ciclo del índice, extracto de la eventual poderes de $q$ a partir de los términos y interpolar el resto en términos de $b.$ El algoritmo puede ser utilizado para calcular las fórmulas de fijo combinaciones de $n$ $k$ como las que en este MSE enlace automáticamente.

Obtenemos para $(n,k) = (3,3)$ $$1/18\,{q}^{3}+1/3\,{b}^{2}-1/6\,{q}^{2}-{\frac {11\,b}{9}}+q/3+2/3$$ y efectivamente, comparándola con la de vincular estos son los valores de la derecha.

Suponiendo ahora que estamos interesados en la divisibilidad por cinco de tres elementos de los subconjuntos es decir, el par $(n,k) = (3,5)$ encontramos

$$1/12\,{b}^{4}-{\frac {13\,{b,}^{3}}{15}}+1/30\,{ q}^{3}+{\frac { 181\,{b,}^{2}}{60}}-1/10\,{ q}^{2}-{\frac {127\,b}{30}}+p/15+2$$

que da la secuencia (a partir de $q=3$)

$$0, 0, 2, 4, 7, 11, 16, 24, 33, 44, 57, 72, 91, \ldots$$

Para el par $(11,5)$ obtenemos

$${\frac {{q}^{11}}{199584000}}-{\frac {{q}^{10}}{3628800}}+{ \frac {{q}^{9}}{151200}}-{\frac {11\,{q}^{8}}{120960}}+{\frac { 683\,{q}^{7}}{864000}}+{\frac {{b}^{4}{q}^{2}}{1200}}\\-{\frac { 781\,{q}^{6}}{172800}}-{\frac {{b}^{4}q}{80}}-{\frac {{b}^{3}{q }^{2}}{120}}+{\frac {31063\,{q}^{5}}{1814400}}+1/24\,{b}^{4}+1/ 8\,{b}^{3}q+{\frac {7\,{b}^{2}{q}^{2}}{240}}\\-{\frac {1529\,{p}^ {4}}{36288}}-{\frac {631\,{b,}^{3}}{1500}}-{\ frac {859\,{b}^{2}q }{2000}}-{\frac {137\,b{q}^{2}}{3000}}+{\frac {16103\,{p}^{3}}{ 252000}}+{\frac {863\,{b,}^{2}}{600}}\\+{\ frac {129\,bq}{200}}-{ \frac {419\,{q}^{2}}{12600}}-{\frac {25\,b}{12}}-{\frac {31\,q }{110}}+1$$

que da la secuencia (a partir de $q=11$)

$$0, 2, 15, 72, 273, 873, 2474, 6363, 15114, 33592, \ldots.$$

Otro par interesante es$(3,6)$, lo que da

$$-{\frac {{b}^{5}q}{90}}-{\frac {{b}^{5}}{90}}+{\frac {7\,{b}^{4 }q}{36}}+1/4\,{b}^{4}-{\frac {23\,{b}^{3}q}{18}}-2\,{b}^{3}+{ \frac {35\,{b}^{2}q}{9}}\\+1/36\,{q}^{3}+7\,{b}^{2}-{\frac {242\, bq}{45}}-1/12\,{q}^{2}-{\frac {313\,b}{30}}+{\frac {17\,q}{6}}+5$$

y $(4,7)$ que produce

$${\frac {{b}^{6}}{360}}-{\frac {3\,{b,}^{5}}{40}}+{\ frac {389\,{b, }^{4}}{504}}+{\frac {{q}^{4}}{168}}-{\frac {215\,{b,}^{3}}{56}}- 1/28\,{q}^{3}\\+{\frac {3041\,{b,}^{2}}{315}}+{\ frac {11\,{p}^{2} }{168}}-{\frac {403\,b}{35}}-q/28+5.$$

El Arce código para esto, incluyendo un total de enumeración de rutina para verificación y algo de código para embellecer a las fórmulas para $k$ pequeño fue de la siguiente manera.

con(planta);

pet_cycleind_set :=
proc(n)
local p, s;
opción de recordar;

 si n=0 entonces devolver 1; fi;

 ampliar(1/n*añadir((-1)^(l+1)*[l]*pet_cycleind_set(n-l), l=1..n));
end;

pet_flatten_term :=
proc(varp)
local terml, d, cf, v;

 terml := [];

 cf := varp;
 para v en indets(varp) ¿
 d := grado(varp, v);
 terml := [op(terml), seq(v, k=1..d)];
 cf := cf/v^d;
od;

 [cf, terml];
end;

V :=
proc(p, n, k)
 local peine, res;
 opción de recordar;

 res := 0;
 peine := firstcomb(q, n);

 mientras que el tipo(peine), haga
 si agregar(p, p en peine) mod k = 0, entonces
 res := res + 1;
fi;

 peine := nextcomb(peine, q);
od;

res;
end;

CF :=
proc(n, k)
 término local, rho, res, p, tv, ixvar, rmd, m,
 rep, qpow, w, ex, vals, val;
 opción de recordar;

 res := 0; rho := exp(2*Pi*I/k);

 durante el plazo en pet_cycleind_set(n) hacer
 plano := pet_flatten_term(plazo);

 para p a k-1 hacer
 vals := []; rep := []; qpow := 0;

 para ixvar en el plano[2] ¿
 ex := p*op(1, ixvar);

 si ex mod k = 0, entonces
 qpow := qpow + 1;
otra cosa
 rep := [op(rep), ixvar];
fi;
od;


 para la rmd para k no
 val := 1;

 para ixvar en rep ¿
 ex := p*op(1, ixvar);
 val := val * añadir(w^(ex*m), m=1..rmd);
od;

 vals :=
 [op(vals), subs(w=rho, expanda(val))];
od;

 res := res + plano[1]*q^qpow *
 interp([seq(b, b=1..k)], vals, b);
od;
od;

 binomial(p,n)/k + res/k;
end;

CFsimp :=
proc(n, k)
 local del formulario, res, plazo, lcf, cnst;
 opción de recordar;

 forma := recopilar(expand(CF(n,k)), {b,q}, `distribuida`);

 cnst := coef(coef(forma a, b, 0), q, 0);

 res := 0;

 para el término en forma-cnst ¿
 lcf := lcoeff(plazo);

 res := res +
simplificar(Re(lcf))*plazo/lcf;
od;

 res + simplificar(cnst);
end;

F :=
proc(vc, n, k)
local de bv;

 si qv mod k = 0, entonces
 bv := k;
otra cosa
 bv := qv mod k;
fi;

 subs({q=qv, b=vb}, CFsimp(n,k));
end;

El lector está invitado a contribuir con una mejor simplificación de rutina hacer un uso más eficaz de la matemática givens. El código de Arce debe ser considerado betaware.

Comentario Sat Jan 23 De 2016. Os presento uno de los casos especiales donde simplificación radical es posible. Inicio de la fórmula

$$\frac{1}{k} {q\elegir n} + \frac{1}{k} \sum_{p=1}^{k-1} \a la izquierda. [z^n] \exp\left(\sum_{i\ge 1} (-1)^{i+1} \frac{z^r}{r} \sum_{m=1}^q w^{rm} \right) \right|_{w=\rho^p}.$$

Ahora supongamos que $q$ es un múltiplo de a $k$ $k$ es un extraño prime. Observe que la suma de $$\sum_{m=1}^q w^{rm}$$ es igual a $q/k\times k = q$ si $pr$ es un múltiplo de a $k$ y cero en caso contrario. Pero $pr$ sólo puede ser un múltiplo de $k$ si $r$ es un múltiplo de a $k.$ Este los rendimientos

$$\frac{1}{k} {q\elegir n} + \frac{1}{k} \sum_{p=1}^{k-1} \a la izquierda. [z^n] \exp\left(\sum_{i\ge 1} (-1)^{kr+1} \frac{z^{kr}}{kr} \sum_{m=1}^q w^{krm} \right) \right|_{w=\rho^p} \\ = \frac{1}{k} {q\elegir n} + \frac{1}{k} \sum_{p=1}^{k-1} \a la izquierda. [z^n] \exp\left(\sum_{i\ge 1} (-1)^{kr+1} \frac{z^{kr}}{kr} \frac{q}{k}\times k \right) \right|_{w=\rho^p} \\ = \frac{1}{k} {q\elegir n} + \frac{1}{k} \sum_{p=1}^{k-1} [z^n] \exp\left(\frac{q}{k} \sum_{i\ge 1} (-1)^{kr+1} \frac{z^{kr}}{r}\right) \\ = \frac{1}{k} {q\elegir n} + \frac{1}{k} \sum_{p=1}^{k-1} [z^n] \exp\left(-\frac{q}{k} \sum_{i\ge 1} \frac{(-z)^{kr}}{r}\right) \\ = \frac{1}{k} {q\elegir n} + \frac{1}{k} \sum_{p=1}^{k-1} [z^n] \exp\left(-\frac{q}{k} \log\frac{1}{1-(-z)^k}\right) \\ = \frac{1}{k} {q\elegir n} + \frac{1}{k} \sum_{p=1}^{k-1} [z^n] (1+z^k)^{q/k}.$$

Por lo tanto, si $n$ es coprime a $k$ obtenemos $$\frac{1}{k} {q\choose n}$$

y si es un múltiplo de a $k$

$$\frac{1}{k} {q\elegir n} + \frac{k-1}{k} {q/k\elegir n/k}.$$

Answer 3

La respuesta es $\frac{1}{5}\binom{2015}{n}$.

Para cada subconjunto de $n$ elementos (no necesariamente con la suma de varios de $5$) consideran que el conjunto de la $2015$ traducciones de la $n$-set. En otras palabras, si tenemos $\{a_1,a_2\dots a_n\}$ Considera a la familia de los conjuntos de la forma$\{r(a_1+k),r(a_2+k),\dots r(a_3+k)\}$$k\in\{0,1,\dots 2015\}$, y donde $r(m)$ es simplemente el más pequeño entero positivo congruente a $m\bmod 2015$.

Se debe tener claro este se divide el $n-sets$ a $\binom{2015}{n}/2015$ de familias, cada una conteniendo $2015$ conjuntos.

Por otra parte, la suma de los conjuntos de la familia de $\{a_1,a_2\dots a_{2015}\}$ son congruentes:

$S,S+n,S+2n,\dots ,S+2015n$ donde $S=a_1+a_2+\dots + a_n$

Debido a $n$ es coprime con $5$ deducimos $\{S,S+n,S+2n\dots S+4n\}$ es una completa residir sistema de $\bmod 5$, así como el $\{S+5n,S+6n,S+7n,S+8n, S+9n\}$ etcétera. Debido a esto, exactamente $2015/5$ de los conjuntos de cada familia tienen cantidades que son múltiplos de $5$. El resultado de la siguiente manera.