edited by
557 views

3 Answers

Best answer
7 votes
7 votes

U = {1, 2, 3, 4, 5}.  Let all the subsets of U corresponds to the vertices of a Graph G. There will be 2^5 vertices in G. There is an edge between two vertices say A and B, When n(AB) = 2 , More ever it is given in the question A != B..  A and B are two subset of U they can have common element.
Now the total number of such order pair (A, B) will be twice the no. of edges in the graph. Because (A, B) will be different order pair than (B, A). So an edge between A and B should be counted twice. Also we already know that 2 * (No. of Edges) =  Sum of degree of all the vertices in G.

Degree of a vertex having no element of U (Empty set)  is 0.
Degree of a vertex containing 1 element of U is also 0.


Degree of a vertex containing two elements : Let say vertex is X = {1, 2}. X will be connected to all the superset of X. X can't connect with itself as mentioned in the question. Now element 3, 4, 5 may or may not present in superset of A. So for each we have 2 cases. So Degree of X is  (2^3 -1). We do -1 because we are not including the case when all three elements 3, 4 and 5 not included because in that case X will be connected to X, which is not allowed.

No of two elements subsets of U is 5C2.
So sum of degree of all the two element set = 5C2 * (2^3 -1) = 70.

Degree of a vertex containing Three elements: Let say vertex is X = {1, 2, 3}. X will be connected with those vertices which contains exactly two elements of X. So no of ways we can select two elements of X is 3C2. Now among the 4 and 5 element we may included them or not. So degree of X = 3C2 * (2^2).

No. of three elements subsets of U = 5C3.
So sum of degree of all the three element sets = 5C3 * 3C2 * (2^2). = 120.

Degree of a vertex containing Four elements : Similar approach. Let X = {1, 2, 3, 4}. X will be connected with those vertices which contains exactly two elements of X. So no of ways we can select two elements is 4C2. Now the 5 element we may or may not include So for 5 we have 2 choices. Therefore degree of X = 4C2 * 2.

No. of such four elements subsets of U = 5C4.
So sum of degree of all the four element sets = 5C4 * 4C2 * 2. = 60

Degree of a vertex containing Five elements : Let X = {1, 2, 3, 4, 5}. This set will be connected to all the 2 element subset of U.
So its degree is 5C2 = 10.

Answer: 0 + 0 + 70 + 120 + 60 + 10 = 260.

selected by
6 votes
6 votes

$$\begin{align*} & X \text{ contains} \;\; 0 \;\; \text{ elements } : \text{ pairs count } = 2^3 - 1 \\ & X \text{ contains} \;\; 1 \;\; \text{ elements } : \text{ pairs count } = \binom{3}{1} * \left ( 2^2 \right ) \\ & X \text{ contains} \;\; 2 \;\; \text{ elements } : \text{ pairs count } = \binom{3}{2} * \left ( 2^1 \right ) \\ & X \text{ contains} \;\; 3 \;\; \text{ elements } : \text{ pairs count } = \binom{3}{3} * \left ( 2^0 \right ) \\ \\ \hline \\ \\ & \text{ Total } = \binom{5}{2} * \left [ 7 + 12 + 6 + 1 \right ] = 10 * 26 = 260 \end{align*}$$

No need to count again for B, as all cases are covered.

edited by
2 votes
2 votes

5C2 * ( 7 + 12 + 6 + 1 ) = 10 * 26 = 260

Answer:

Related questions

5 votes
5 votes
2 answers
1
Bikram asked May 24, 2017
562 views
Let $S$ be the set $\{1,2,3, \dots ,8\}$. Let $n$ be the number of sets of two non-empty disjoint subsets of $S$. The value of $n$ is _______.
5 votes
5 votes
1 answer
2
Bikram asked May 24, 2017
475 views
Total number of ways we can fill a $4 \times 4$ matrix by $0$ and $1$’s such that every row and column contains odd no of $0$'s and $1$'s is ________.
3 votes
3 votes
1 answer
3
Bikram asked May 24, 2017
274 views
$O(G) = 12$ and $G$ is cyclic. The total number of generators possible in $G$ are __________.
8 votes
8 votes
3 answers
4
Bikram asked May 24, 2017
408 views
See the above table of a,b,c,d. The total number of subgroups possible from the above diagram are _______.