Encuentre el número de conjuntos de cardinalidad$m$ que son subconjuntos de$\{1,\cdots,n\}$ de manera que la suma de los elementos del subconjunto sea divisible por$k$.

Question

Para casos específicos con números pequeños, esto funciona con bastante facilidad usando enumeración directa y aritmética modular. Sin embargo, mi pregunta es: ¿cómo resolvemos este problema en general?

Answer 1

Se puede calcular el número de $m$-elemento de subconjuntos de a $\{1 \ldots n\}$ cuando la suma de los elementos en el subconjunto es igual a $k$ con la generación de la función $\displaystyle\prod_{i=1}^n(1+xy^i)$, examinando el coeficiente de $x^my^k$. Para obtener el número de subconjuntos cuya suma es divisible por $k$, se puede simplemente sumar los coeficientes de $x^my^K$ para todos los múltiplos $K$$k$. Sin embargo, lo más probable es computacionalmente eficiente para expandir la generación de la función del producto en el polinomio cociente del anillo de $\mathbb{Z}[x,y]/\left<y^k-1\right>$; a continuación, el número que usted está buscando es el coeficiente de $x^m$.

No sé si Mathematica permite calcular de esta manera, pero el Magma. Puedes probarlo en el Magma de la calculadora en línea, con el siguiente código de ejemplo:

m:=2; k:=3; Z<x,y>:=PolynomialRing(Integers(),2); X:=quo<Z|y^k-1>; for n in {1..20} do z:=&*[X!(1+x*y^i):i in {1..n}]; n,Coefficient(Coefficient(z,1,m),2,0); end for;

Este código comprueba los resultados en Julián Aguirre comentario anterior.