INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More 

April 5, 2020

Counting Principle - Concept with Problem | Combinatorics

Learn the concept of the Counting Principle and make algorithms to count complex things in a simpler way with the help of a beautiful problem of Combinatorics.

Concept - Counting Principle.


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$

Key Concepts


Combinatorics

Counting

Set Theory

Check the Answer


Answer: $180$

Try with Hints


Understand The Problem :

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]

Brain_Teaser : Generalize the concept

What if the set $S=\{1,2,\ldots,n\}$ i.e., Find the number of subsets $A$ of $S=\{1,2,\ldots,n\}$ such that $x\in A, $ and $2x \in S \Rightarrow 2x \in A$



Subscribe to Cheenta at Youtube


2 comments on “Counting Principle - Concept with Problem | Combinatorics”

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com
enter