On the Number of Subsets Divisible by \(k\)
In my first post, I want to discuss an elementary combinatorics problem. Somewhat surprisingly, considering complex numbers provides a very slick solution. The problem is as follows: how many subsets of \(n\) elements have size divisible by \(k\)?
I first want to consider the case when \(k = 2\). Now we are simply asking how many subsets of \(\{1,...,n\}\) have an even number of elements. If you have never seen this problem before, you may want to take a few minutes to think about it before continuing.
The solution involves the idea of "toggling" one of the elements in the set. Given a subset \(S\subset \{1,...,n\}\), consider the subset \(S\oplus \{1\}\), where we add the element \(1\) to \(S\) if \(S\) does not already contain \(1\), and remove it otherwise. It is clear that if \(S\) has an even number of elements, then \(S\oplus \{1\}\) will have an odd number of elements and vice versa. We also easily verify that \((S\oplus \{1\})\oplus\{1\} = S\). Thus, toggling \(1\) is a bijection between the even and odd subsets of \(\{1,...,n\}\) and thus the number of subsets of even and odd size must be equal (and so must be \(2^{n-1}\)). (The astute reader may have noticed that there is one case excluded from this argument, namely if \(n = 0\). In this case there are no elements to toggle, and indeed there is one even subset (the empty set), but there are no odd subsets.)
Our goal now is to investigate what happens when \(k > 2\), i.e. we want to generalize even to divisible by 3, etc. The key is to write the number of subsets with a multiple of \(k\) elements as
\[f_k(n) = \binom{n}{0} + \binom{n}{k} + \binom{n}{2k} + ... \]
and to use complex \(k\)-th roots of unity to rewrite this as
\[\begin{equation}\label{fundamental lemma}f_k(n) = \frac{1}{k}\Sigma_{i=1}^{k} (1+\omega_k^i)^n\end{equation}\]
where \(\omega_k = e^{\frac{2i\pi}{k}}\) is a primitive \(k\)-th root of unity.
To prove identity \(\ref{fundamental lemma}\) we expand \((1+\omega_k^i)^n\) using the binomial theorem and change the order of summation
\[\frac{1}{k}\Sigma_{i=1}^{k} (1+\omega_k^i)^n = \frac{1}{k}\Sigma_{i=1}^k \Sigma_{j=0}^n \binom{n}{j}\omega_k^{ij} = \frac{1}{k}\Sigma_{j=0}^n \binom{n}{j}\Sigma_{i=1}^k (\omega_k^j)^i = \binom{n}{0} + \binom{n}{k} + \binom{n}{2k} + ... \]
where \(\Sigma_{i=1}^k (\omega_k^j)^i = 0\) if \(j\nmid k\) from the formula for the sum of geometric series (if \(j\mid k\) then \(\omega_k^j = 1\) and the sum is \(k\)).
We will now show how to use identity \(\ref{fundamental lemma}\) to gain insight into the problem. First, for large \(n\), we would expect that about \(1/k\) subsets would have size divisible by \(k\). We can show this from the following identity
\[\frac{f_k(n)k}{2^n} = \frac{\Sigma_{i=1}^{k} (1+\omega_k^i)^n}{2^n} = 1 + \Sigma_{i=1}^{k-1}\left(\frac{1 + \omega_k^i}{2}\right)^n\]
where we have used that \(\omega_k^k = 1\). We can easily see that \(\left|\frac{1 + \omega_k^i}{2}\right| < 1\) for each of the \(i = 1,...,k-1\) which immediately implies that
\[\lim_{n\rightarrow \infty} \frac{f_k(n)k}{2^n} = 1\]
So we see that about \(1/k\) of the subsets have a number of elements divisible by \(k\) for large \(n\).
For large \(k\), this is really all that we can say. However, for small values of \(k\), we can say more. For instance, if \(k = 2\), then \(\omega_2 = -1\) and only the one term in \(\ref{fundamental lemma}\) survives, which recovers the result that \(f_2(n) = 2^{n-1}\).
Remarkably, for \(k = 3\), we can say more as well. We note that that \(|1 + \omega_3^i| = 1\) for \(i = 1,2\). In fact, \(1 + \omega_3\) and \(1 + \omega_3^2\) are sixth roots of unity which are inverses of each other. Using this fact and formula \(\ref{fundamental lemma}\), we can show the following
\(f_3(n) = \frac{2^n+r}{3}\) where \(r = 2\) if \(n\equiv 0\pmod{6}\), \(r = -2\) if \(n\equiv 3 \pmod{6}\), \(r = 1\) if \(n\equiv 1,5 \pmod{6}\),
and \(r = -1\) if \(n\equiv 2,4 \pmod{6}\)
For larger values of \(k\), more of the complex numbers \(1 + \omega_k^i\) have norm larger than \(1\) and so in general, the difference between \(f_k(n)\) and \(2^n/k\) will grow exponentially with \(n\) (unlike \(k = 2,3\) where this difference remained small and bounded for all \(n\)). However, for \(k = 4\) and \(k = 6\), all but two of the \(1 + \omega_k^i\) (with \(i\neq k\)) have norm smaller than \(1\). Moreover, these two complex numbers are inverses and appropriate powers of them lie entirely on the imaginary axis. Thus in equation \(\ref{fundamental lemma}\), their contributions cancel for special values of \(n\). This allows us to obtain the following two results.
\(f_4(n) = \frac{2^n}{4}\) if \(n\equiv 2\pmod{4}\)
\(f_6(n) = \frac{2^n-2}{6}\) if \(n\equiv 3\pmod{6}\)
I challenge the reader to find purely combinatorial proofs of the statements we've obtained for \(k = 3,4\) and \(6\), which I suspect is a very difficult task (we gave a purely combinatorial proof for \(k=2\) at the beginning). This represents an instance where introducing seemingly unrelated, more advanced mathematics simplifies an elementary problem.
I first want to consider the case when \(k = 2\). Now we are simply asking how many subsets of \(\{1,...,n\}\) have an even number of elements. If you have never seen this problem before, you may want to take a few minutes to think about it before continuing.
The solution involves the idea of "toggling" one of the elements in the set. Given a subset \(S\subset \{1,...,n\}\), consider the subset \(S\oplus \{1\}\), where we add the element \(1\) to \(S\) if \(S\) does not already contain \(1\), and remove it otherwise. It is clear that if \(S\) has an even number of elements, then \(S\oplus \{1\}\) will have an odd number of elements and vice versa. We also easily verify that \((S\oplus \{1\})\oplus\{1\} = S\). Thus, toggling \(1\) is a bijection between the even and odd subsets of \(\{1,...,n\}\) and thus the number of subsets of even and odd size must be equal (and so must be \(2^{n-1}\)). (The astute reader may have noticed that there is one case excluded from this argument, namely if \(n = 0\). In this case there are no elements to toggle, and indeed there is one even subset (the empty set), but there are no odd subsets.)
Our goal now is to investigate what happens when \(k > 2\), i.e. we want to generalize even to divisible by 3, etc. The key is to write the number of subsets with a multiple of \(k\) elements as
\[f_k(n) = \binom{n}{0} + \binom{n}{k} + \binom{n}{2k} + ... \]
and to use complex \(k\)-th roots of unity to rewrite this as
\[\begin{equation}\label{fundamental lemma}f_k(n) = \frac{1}{k}\Sigma_{i=1}^{k} (1+\omega_k^i)^n\end{equation}\]
where \(\omega_k = e^{\frac{2i\pi}{k}}\) is a primitive \(k\)-th root of unity.
To prove identity \(\ref{fundamental lemma}\) we expand \((1+\omega_k^i)^n\) using the binomial theorem and change the order of summation
\[\frac{1}{k}\Sigma_{i=1}^{k} (1+\omega_k^i)^n = \frac{1}{k}\Sigma_{i=1}^k \Sigma_{j=0}^n \binom{n}{j}\omega_k^{ij} = \frac{1}{k}\Sigma_{j=0}^n \binom{n}{j}\Sigma_{i=1}^k (\omega_k^j)^i = \binom{n}{0} + \binom{n}{k} + \binom{n}{2k} + ... \]
where \(\Sigma_{i=1}^k (\omega_k^j)^i = 0\) if \(j\nmid k\) from the formula for the sum of geometric series (if \(j\mid k\) then \(\omega_k^j = 1\) and the sum is \(k\)).
We will now show how to use identity \(\ref{fundamental lemma}\) to gain insight into the problem. First, for large \(n\), we would expect that about \(1/k\) subsets would have size divisible by \(k\). We can show this from the following identity
\[\frac{f_k(n)k}{2^n} = \frac{\Sigma_{i=1}^{k} (1+\omega_k^i)^n}{2^n} = 1 + \Sigma_{i=1}^{k-1}\left(\frac{1 + \omega_k^i}{2}\right)^n\]
where we have used that \(\omega_k^k = 1\). We can easily see that \(\left|\frac{1 + \omega_k^i}{2}\right| < 1\) for each of the \(i = 1,...,k-1\) which immediately implies that
\[\lim_{n\rightarrow \infty} \frac{f_k(n)k}{2^n} = 1\]
So we see that about \(1/k\) of the subsets have a number of elements divisible by \(k\) for large \(n\).
For large \(k\), this is really all that we can say. However, for small values of \(k\), we can say more. For instance, if \(k = 2\), then \(\omega_2 = -1\) and only the one term in \(\ref{fundamental lemma}\) survives, which recovers the result that \(f_2(n) = 2^{n-1}\).
Remarkably, for \(k = 3\), we can say more as well. We note that that \(|1 + \omega_3^i| = 1\) for \(i = 1,2\). In fact, \(1 + \omega_3\) and \(1 + \omega_3^2\) are sixth roots of unity which are inverses of each other. Using this fact and formula \(\ref{fundamental lemma}\), we can show the following
\(f_3(n) = \frac{2^n+r}{3}\) where \(r = 2\) if \(n\equiv 0\pmod{6}\), \(r = -2\) if \(n\equiv 3 \pmod{6}\), \(r = 1\) if \(n\equiv 1,5 \pmod{6}\),
and \(r = -1\) if \(n\equiv 2,4 \pmod{6}\)
For larger values of \(k\), more of the complex numbers \(1 + \omega_k^i\) have norm larger than \(1\) and so in general, the difference between \(f_k(n)\) and \(2^n/k\) will grow exponentially with \(n\) (unlike \(k = 2,3\) where this difference remained small and bounded for all \(n\)). However, for \(k = 4\) and \(k = 6\), all but two of the \(1 + \omega_k^i\) (with \(i\neq k\)) have norm smaller than \(1\). Moreover, these two complex numbers are inverses and appropriate powers of them lie entirely on the imaginary axis. Thus in equation \(\ref{fundamental lemma}\), their contributions cancel for special values of \(n\). This allows us to obtain the following two results.
\(f_4(n) = \frac{2^n}{4}\) if \(n\equiv 2\pmod{4}\)
\(f_6(n) = \frac{2^n-2}{6}\) if \(n\equiv 3\pmod{6}\)
I challenge the reader to find purely combinatorial proofs of the statements we've obtained for \(k = 3,4\) and \(6\), which I suspect is a very difficult task (we gave a purely combinatorial proof for \(k=2\) at the beginning). This represents an instance where introducing seemingly unrelated, more advanced mathematics simplifies an elementary problem.
Comments
Post a Comment