¿Cómo puedo contar los subconjuntos de un conjunto cuyo número de elementos es divisible por 3? 4?

Question

Dejemos que $S$ sea un conjunto de tamaño $n$ . Hay una manera fácil de contar el número de subconjuntos con un número par de elementos. Algebraicamente, viene del hecho de que

$\displaystyle \sum_{k=0}^{n} {n \choose k} = (1 + 1)^n$

mientras que

$\displaystyle \sum_{k=0}^{n} (-1)^k {n \choose k} = (1 - 1)^n$ .

De ello se desprende que

$\displaystyle \sum_{k=0}^{n/2} {n \choose 2k} = 2^{n-1}$ .

Una prueba combinatoria directa es la siguiente: fijar un elemento $s \in S$ . Si un subconjunto dado tiene $s$ en él, añádalo; en caso contrario, quítelo. Esto define una biyección entre el número de subconjuntos con un número par de elementos y el número de subconjuntos con un número impar de elementos.

Las fórmulas análogas para los subconjuntos con un número de elementos divisible por $3$ o $4$ son más complicados, y se dividen en casos según el residuo de $n \bmod 6$ y $n \bmod 8$ respectivamente. Las derivaciones algebraicas de estas fórmulas son las siguientes (con $\omega$ una tercera raíz primitiva de la unidad): observe que

$\displaystyle \sum_{k=0}^{n} \omega^k {n \choose k} = (1 + \omega)^n = (-\omega^2)^n$

mientras que

$\displaystyle \sum_{k=0}^{n} \omega^{2k} {n \choose k} = (1 + \omega^2)^n = (-\omega)^n$

y que $1 + \omega^k + \omega^{2k} = 0$ si $k$ no es divisible por $3$ y es igual a $3$ de lo contrario. (Este es un caso especial de la transformada discreta de Fourier.) Se deduce que

$\displaystyle \sum_{k=0}^{n/3} {n \choose 3k} = \frac{2^n + (-\omega)^n + (-\omega)^{2n}}{3}.$

$-\omega$ y $-\omega^2$ son raíces sextas de la unidad, por lo que esta fórmula se divide en seis casos (o quizás tres). Observaciones similares sobre las cuartas raíces de la unidad muestran que

$\displaystyle \sum_{k=0}^{n/4} {n \choose 4k} = \frac{2^n + (1+i)^n + (1-i)^n}{4}$

donde $1+i = \sqrt{2} e^{ \frac{\pi i}{4} }$ es un múltiplo escalar de una raíz octava de la unidad, por lo que esta fórmula se divide en ocho casos (o quizás cuatro).

Pregunta: ¿Alguien conoce una prueba combinatoria directa de estas identidades?

Answer 1

Hay una prueba combinatoria muy bonita de la identidad general $$\sum_{k \geq 0} \binom{n}{rk} = \frac{1}{r} \sum_{j=0}^{r-1} (1+\omega^j)^n,$$ para $\omega$ una primitiva $r$ raíz de la unidad, en Benjamin, Chen y Kindred, " Sumas de coeficientes binomiales uniformes ," Revista de matemáticas 83 (5), pp. 370-373, diciembre de 2010.

Muestran que ambas partes cuentan el número de cerradas $n$ -continúa caminando $C_r$ comenzando en el vértice 0, donde $C_r$ es el ciclo dirigido en $r$ elementos con la adición de un bucle en cada vértice, y un paseo es cerrado si termina donde empieza.

Lado izquierdo : Para que un $n$ -Camino para ser cerrado, tiene que tomar $kr$ movimientos hacia adelante y $n-kr$ movimientos estacionarios para algunos $k$ .

Lado derecho : El número de paseos cerrados que comienzan en el vértice $j$ es el mismo independientemente de la elección de $j$ por lo que basta con demostrar que el número total de cerradas $n$ -continúa caminando $C_r$ es $\sum_{j=0}^{r-1} (1+\omega^j)^n.$ Para cada $n$ -correr con el vértice inicial $j$ asignar a cada paso adelante un peso de $\omega^j$ y cada paso estacionario un peso de $1$ . Definir el peso de un $n$ -caminata en sí misma para ser el producto de los pesos de los pasos en la caminata. Así, la suma de los pesos de todos los $n$ -paseos a partir de $j$ es $(1+\omega^j)^n$ y $\sum_{j=0}^{r-1} (1+\omega^j)^n$ da el peso total de todos los $n$ -continúa caminando $C_r$ . El abierto $n$ -se pueden dividir en órbitas de forma que la suma de los pesos de los paseos en cada órbita sea $0$ . Por lo tanto, la apertura $n$ -los paseos aportan un total de $0$ a la suma $\sum_{j=0}^{r-1} (1+\omega^j)^n$ . Dado que un sistema cerrado $n$ -Caminar tiene peso $1$ , $\sum_{j=0}^{r-1} (1+\omega^j)^n$ debe, por tanto, dar el número de cerradas $n$ -continúa caminando $C_r$ .

---

A continuación, hacen una ligera modificación del argumento anterior para dar una prueba combinatoria de $$\sum_{k \geq 0} \binom{n}{a+rk} = \frac{1}{r} \sum_{j=0}^{r-1} \omega^{-ja}(1+\omega^j)^n,$$ donde $0 \leq a < r$ .

---

Benjamin y Scott, en " Coeficientes de la tercera y cuarta binomial " ( Trimestral de Fibonacci , 49 (2), pp. 99-101, mayo de 2011) dan diferentes argumentos combinatorios para los casos concretos por los que preguntas, $\sum_{k \geq 0} \binom{n}{3k}$ y $\sum_{k \geq 0} \binom{n}{4k}$ . Sin embargo, prefiero el argumento más general de arriba, así que dejaré éste como enlace y no lo resumiré.

Answer 2

Fijar dos elementos s ₁ ,s ₂ ∈S y dividir los subconjuntos de S en dos partes (subconjuntos de S que sólo contienen s ₂ )∪(subconjuntos de S que contienen s ₁ si contienen s ₂ ). La segunda parte contiene igual número de conjuntos para todos los recordatorios mod 3 (porque Z/3 actúa allí añadiendo s ₁ , entonces s ₂ y luego eliminando los dos), es decir, 2 n-2 . Y para la primera parte tenemos una biyección con subconjuntos (edición: con 2 elementos mod 3) de un conjunto con (n-2) elementos.

Así obtenemos una relación de recurrencia que da una respuesta 2 n-2 +2 n-4 +... -- es decir, (2 n -1):3 para los pares y (2 n -2):3 para impar n.

---

Errata. Para n=0,1,5 mod 6 hay que añadir "+1" a la respuesta del párrafo anterior (por ejemplo, para n=6 la respuesta correcta es 1+20+1=22 y no 21).

Permítanme que intente reformular la solución para que sea evidente. Para n=2k dividir S en k pares y considerar una acción de un grupo Z/3Z sobre cada par descrito en un primer párrafo. Obtenemos una acción de (Z/3Z) k en subconjuntos de S, y tras eliminar su único punto fijo (conjunto de k elementos formado por los segundos puntos de cada par) obtenemos una biyección entre subconjuntos que tienen 0, 1 o 2 elementos mod 3. Así que hay (2 n -1):3 conjuntos con i mod 3 elementos excluyendo el punto fijo y para contar ese punto hay que añadir "+1" para i=k mod 3.

Y para n=2k+1 hay 2 puntos fijos -que incluyen o no el (2k+1)- elemento de S- con k+1 y k elementos respectivamente.

Answer 3

Intento añadir detalles con un cálculo sencillo:

por ejemplo, muestro $\binom{n}{1}+\binom{n}{3}+\binom{n}{6}+\cdots=\frac{1}{3}[2^n+2\cos(\frac{n\pi}{3})]$

sabemos $(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n$ por lo que si en esta identidad ponemos $1,\alpha,\alpha^2$ donde $\alpha=\cos\frac{2\pi}{3}+i\sin(\frac{2\pi}{3})$ respectivamente, entonces obtenemos $$2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots$$ , $$(1+\alpha)^n=\binom{n}{0}+\binom{n}{1}\alpha+\binom{n}{2}\alpha^2+\binom{n}{3}\alpha^3+\cdots$$ ,

$$(1+\alpha^2)^n=\binom{n}{0}+\binom{n}{1}\alpha^2+\binom{n}{2}\alpha^4+\binom{n}{3}\alpha^6+\cdots$$

pero si $3\nmid n$ entonces podemos ver fácilmente que $1+\alpha^k+\alpha^{2k}=3$ por lo que

$2^n+(1+\alpha)^n+(1+\alpha^2)^n=3\{\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\cdots\}$ pero como $1+\alpha+\alpha^{2}=0$ por lo que

$1+\alpha=-\alpha^2=\cos(\frac{\pi}{3})+i\sin(\frac{\pi}{3})$ y también $1+\alpha^2=-\alpha=\cos(\frac{\pi}{3})-i\sin(\frac{\pi}{3})$ por lo que $$2^n+(1+\alpha)^n+(1+\alpha^2)^n=2^n+2\cos(\frac{n\pi}{3})$$ para que obtengamos el resultado deseado.