2

In how many ways we can make pairs (Both elements must be from different groups) i.e. if we have two sets, $A=\{1,2\}$ and $B=\{3,4\}$, it's simple we can make $(1,3)$ $(2,4)$ $(1,4)$ $(2,3)$ only four pairs can be obtained

if we have $A=\{1,2,3,4\}$, $B=\{5,6\}$, $C=\{7,8\}$

I think we can make 20 pairs for them. correct me if I am wrong . and i need general formula for this. Thanks in advance.

while
  • 105
Altaf Hussain
  • 21

2 Answers2

3

The set of all possible ordered pairs is called the Cartesian product, symbolized by $\times$.

$$A \times B \equiv \{(a,b) \space | \space a \in A, b \in B \}$$

The number of pairs (number of elements in the product):

$$|A \times B| = |A||B|$$

user76568
  • 4,542
  • Why do you subtract the intersection? – Aharon Sep 17 '14 at 10:05
  • Because I got confused. Thanks. :) – user76568 Sep 17 '14 at 10:08
  • does this mean just multiply the number of elements in a set like 4 x 2 x 2=16 ? – Altaf Hussain Sep 17 '14 at 12:29
  • Unless you simply want to count 3-tuples, which obviously you don't, then you need realize that: OK, put $A$ to the left of $\times$. But now, do you put $B$ or $C$ to the right? maybe $B \cup C$? Think about it. (For 3 sets, just multiplying the 3 sizes will give you the correct number only when $B \cap C = \emptyset$) – user76568 Sep 17 '14 at 12:39
0

A more general way to construct the formula:
Suppose that you have n sets, $A_1, \cdots A_n,$ where some element may be in more that one set. An example would be to revise your original example by changing $C$ from $\{7,8\}$ to $\{6,7\}.$

Let $f(A_i)$ denote the number of distinct elements in all of the $(n-1)$ sets combined other than $A_i.$
In the revised example, where $A_1$ is set to $A = \{1,2,3,4\},$ then $f(A_1)$ would = 3.

Let $g(A_i)$ denote the number of (presumably distinct) elements in $A_i.$
Let $h(A_i)$ denote the number of elements in $A_i$ that are also in at least one of the (n-i) sets $A_{i+1}, \cdots, A_n.$

Then the possible number of ordered pairs will be $\sum_{i=1}^n \{f(A_i) \times g(A_i)\} - h(A_i).$

The reason that $h(A_i)$ is relevant is best visualized by example. Suppose that the original example is further refined so that $A_1 = \{1,2,5,6\}.$

Then, the normal formula $\sum_{i=1}^n \{f(A_i) \times g(A_i)\}$ would count (5,5) twice and count (6,6) three times.

user2661923
  • 35,619
  • 3
  • 17
  • 39