Counting Principle - Concept with Problem | Combinatorics

Often we come across such problems that involves very complex counting which are nearly impossible to do in a trivial way. To encounter this kind of complexity of counting we use some $\textbf{tricks and tools}$; one of them is to find a algorithm or a pattern.

We try to obtain result for a similar but a simpler problem and then by the algorithm achieve the final goal.

One Handy Tool - Multiplication Principle and Its Application In Set Theory

Suppose we have two sets $X=\{x_1,x_2,x_3\}$ and $Y=\{y_1,y_2\}$ ,then number of order pairs $(x_i,y_j);\text{ such that } i=1,2,3 ; j=1,2$ is equal to $3\times2=6$

That is , If a set $S_1$ has $n$ elements and the set $S_2$ has $m$ element then the set $S_1\times S_2=\{(a,b) | a \in S_1 , b \in S_2\}$ has $nm$ elements.

Face the problem Now :

Let $S=\{1,2,3,\ldots ,10\}$ Find the number of subsets $A$ of $S$ such that $x\in A, $ and $2x \in S \Rightarrow 2x \in A$

What is the set $A$? Let us see some feasible options for $A$

$\{1,2,4,8\}$, $\{2,4,8\}$, $\{1,3,2,4,8,6\} \ldots \text{etc.}$Is there any pattern ?

Ok wait !!!! There is one thing that if we take $1$ in $A$ then $2,4,8$ must belongs to $A$, similarly, if we take $3 \in A$ then $6\in A$ .

Good.... we are surely getting something interesting. Do you want to give it a thought ?

Let's Take a Simpler Example :

Let us see what happens if $S$ was given as $\{1,2,3\}$ , then all possible options of $A$ would be $\{1,2\}$, $\{2\}$, $\{3\}$, $\{2,3\}$, $\phi$. i.e, $6$ such possible options.

We can notice a very interesting thing here that the elements $1,2$ are making a group because twice of $1$ is $2$ let call them elements of $1^{st}$ kind and $3$ is not related to the elements by this kind of relation, let's call it element of 2^{nd} kind.

Then we can make two collection of sets $X=\{\{1,2\},\{2\},\phi \}$ and $Y=\{\{3\},\phi\}$ [That is $X$ contains all the subsets made by the elements of $1^{st}$ kind following the rule and $\phi$, similarly $Y$ contains the sets made by the elements of $2^{nd}$ kind following the rule and $\phi$ ].

Now , Let $P$ be the set $\{X'\cup Y' | \text{where} X' \in X \text{ and } Y' \in Y \}$ . Then member of $P$ are the possible options for $A$.

Therefore, $|P|=$ number of possible subset $A$ [where $|| \to $ number of elements in a set]. By the Multiplication Principle

$|P|=|X|\times |Y|=3\times 2=6$.

Finally, we have got a pattern. But !!! it will be better to check it for one more simpler example then we can definitely apply it to solve the original problem. Can you verify it for $S=\{1,2,3,4\}$

See!! we are getting a really good result.

For $S=\{1,2,3,4\} $

The element(s) of $1^{st}$ kind is/are : $1,2,4$.

The element(s) of $2^{nd}$ kind is/are : $3$ .

Then $X$=$\{\{1,2,4\}$, $\{2,4\}$, $\{4\}$, $\phi\}$; $\quad Y$= $\{\{3\},\phi\}$ .

Then $|P|=|X|\times |Y|=4\times 2=8$.

Now, if you count the possible subsets $A$ , you will get the same result. [They are $\{1,2,4\}$, $\{2,4\}$, $\{4\}$, $\{3\}$, $\{1,2,3,4\}$, $\{2,3,4\}$, $\{3,4\}$, $\phi $]. So it works for $S$=$\{1,2,3,4\}$ .

Now you can easily apply the algorithm to the original problem.

Applying the algorithm for the original problem :

$S={1,2,3,\ldots,10}$..

Elements of $1^{st}$ kind : $1,2,4,8$.

Elements of $2^{nd}$ kind : $3,6$.

Elements of $3^{rd}$ kind : $5,10$.

Elements of $4^{th}$ kind : $7$

Elements of $5^{th}$ kind : $9$

Here $X$=$\{\{1,2,4,8\}$, $\{2,4,8\}$, $\{4,8\}$, $\{8\}$, $\phi\}$

$Y$=$\{\{3,6\}$, $\{6\}$, $\phi\}$

$Z$=$\{\{5,10\}$, $\{10\}$, $\phi\}$

$W=\{\{7\},\phi\}$

$U=\{\{9\},\phi\}$

$|P|=|X|\times|Y|\times|Z|\times|W|\times |U|$

$=5\times 3\times 3\times 2\times 2=180$ [ANS]