Animated Solution for Mathematics - Permutations and Combinations: Let $S=\{1,2,3,4,5,6,9\}$. Then the number of elements in the set $T=\{A\subseteq S:A\ne \varphi \text{ and the sum of all the elements of }A\text{ is not a multiple of 3}\}$ is .

Imagine you are standing before a collection of numbers: $S=\{1,2,3,4,5,6,9\}$. Your task is to find how many non-empty subsets of this collection have a sum that is not a multiple of 3.

With 7 elements, there are $2^7-1=127$ non-empty subsets. Listing them would be a nightmare of manual labor and inevitable mistakes. Today, we are going to solve this using the elegance of generating functions and the magic of complex roots of unity.

Before we dive into the math, let's organize our battlefield. We care about the sum modulo 3. Every number in our set $S$ falls into one of three buckets based on its remainder when divided by 3:

- Remainder 0 ($R_0$): $\{3,6,9\}$ - Remainder 1 ($R_1$): $\{1,4\}$ - Remainder 2 ($R_2$): $\{2,5\}$

This categorization is our secret weapon. It allows us to see the structure of the problem before we even write an equation.

Our Mathematical Bookkeeper

We define a polynomial $P(x)=(1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)(1+x^6)(1+x^9)$. Think of each factor $(1+x^s)$ as a decision: you either choose not to include the number $s$ (represented by the $1$) or you include it (represented by the $x^s$).

When you multiply these factors, the exponent of $x$ in the resulting term is the sum of the elements in that subset. If we expand this, we get $P(x)=\sum a_k{x}^k$, where $a_k$ is the number of subsets that sum to $k$. Our goal is to find the sum of all $a_k$ where $k$ is not a multiple of 3.

This is where the magic happens. We know that the total number of subsets is $P(1)=(1+1{)}^7=2^7=128$. To isolate the sums that are multiples of 3, we use the complex cube root of unity, $\omega$, where ${\omega }^3=1$ and $1+\omega +{\omega }^2=0$.

By evaluating $P(\omega )$, we create a filter that picks out the coefficients $a_k$ based on their index modulo 3. Substituting $x=\omega$ into our polynomial, we get:

Using the properties of $\omega$, this simplifies beautifully:

Since $1+\omega =-{\omega }^2$ and $1+{\omega }^2=-\omega$, we have:

We now have $P(\omega )=a_0+a_1\omega +a_2{\omega }^2=8$. Since $a_0,a_1,a_2$ are real, we use the identity ${\omega }^2=-1-\omega$ to equate the real and imaginary parts.

This leads us to $a_1=a_2$ and $a_0=a_2+8$. Substituting these into the total sum $a_0+a_1+a_2=128$, we find:

Thus, $a_1=40$ and $a_0=48$. The number of subsets with a sum that is a multiple of 3 is $a_0=48$. However, this includes the empty set (sum = 0).

So, there are $48-1=47$ non-empty subsets with a sum divisible by 3. The total number of non-empty subsets is $127$. Therefore, the number of subsets whose sum is not a multiple of 3 is: