if A ,  B  are subsets of  {1,2,3,4,5}  How many ordered pairs  (A,B)  have: |A∩B|=1
122875
How many ordered pairs $(A,B)$ they are if $A$ and $B$ are subsets of $\{ 1,2,3,4,5 \}$ such that $A \cap B = \{1\}$?  If 1 is in both sets :  Size of $A$ is $&gt;1$ and size of $B$ is $&gt;1$.  $\Rightarrow$ Size of $A \cup B =4$  $$5 \cdot (3 \cdot 3 \cdot 3 \cdot 3) = 405$$ is not correct.  What am I missing here?
63412
Prove:  $(A\cup B) \cap C \subseteq A\cup (B\cap C)$  How could I go about proving this?
82869
A set $M = \{1,2,\ldots,100\}$ is divided into seven subsets with no number in $2$ or more subsets. How do you prove that one subset either contains four numbers $a$, $b$, $c$, and $d$ such that $$a + b = c + d$$ or three numbers $p$, $q$, and $r$ such that $$p + q = 2r\,?$$ I am having some issues with this question whether I don't fully understand the question or my arithmetic is wrong. Grateful for any help.
16314
Greetings Community! The above problem you see is a combinatorics problem I could not solve. :( This problem is from ZIO $2010$, P$1$.     Here is what I did: Observe that every graph can be divided into "sub-groups" which may help in solving. We first remove the empty set. Then the singleton set. Consider the bigger but smaller than the sub-parts example:    The singleton sets are $\{4,5,6\}$ which are at the least position in the graph.   The dual sets are $\{2,4\}, \{3,5\}, \{3,6\}$, the bottom - two portions in the graph. The triplet sets are $\{2,4,5\}, \{4,5,6\}$ which we may manually count but for the bigger graphs in the sub-part, this may prove to be difficult and this is where I am stuck.   Any help would be appreciated. Thanks.
102924
Q.20 What is the number of ordered pairs $(𝐴, 𝐵)$ where $𝐴$ and $𝐵$ are subsets of $\{1,2, . . . ,5\}$ such that neither $𝐴 ⊆ 𝐵$ nor $𝐵 ⊆ 𝐴$?  Ans: 𝟓𝟕𝟎  Hint: Use principle of Inclusion-Exclusion.  Solution: Let $X$ denote the set of all ordered pairs $(A, B)$ when $A ⊆ B$. Similarly let $Y$ denote set of all ordered pairs $(A,B)$ when $B ⊆ A$. The question asks to find $$𝑛(X'\cap Y') = 𝑛(𝑆) − 𝑛(𝑋\cup𝑌) $$$$= 𝑛(S) − 𝑛(X) − 𝑛(Y) + 𝑛(X\cap Y) $$$$= 2^{10} − 3^5 − 3^5 + 2^5 = 570$$.    How did this happen? What is $S$? If $S={1,2,3,4,5}$, shouldn't $n(S)=2^5$? And where do the $3^5$s come from? I cannot understand this.  Also, are there other ways to solve this?
42309
Assume I have a non-empty finite set $S$ with $x=|S|$. I want to divide the set $S$ into subsets $S_1, S_2, .., S_n$ (Edit: Yes, $S = \cup S_i$, and I'm embarrassed that I forgot to include that) such that:     $ |S_i| = y, \forall 1 \le i \le n$  (The cardinality of each subset is fixed)   $|S_i \cap S_j| = 1, \forall 1 \le i,j \le n, i \neq j$ (Each subset has exactly 1 element in common with any other subset)   Edit: The second condition above excludes the possiblility of a pairwise disjoint division of subsets.  Is there a way to determine the maximum value of $n$ (the number of possible subsets), given $x$ and $y$?
82285
We can see subsets as combinations of unspecified length of a set's elements, and there are, of course,   $$\sum_{k=0}^n {n \choose k}=2^n$$   subsets of a set with $n$ elements.  I was wondering whether there is a neat expression (analogous to $2^n$) for  the number of permutations of unspecified length of the elements of a set.    For example, if we have five distinct items, the number of permutations for each possible length is given below; the total number of permutations (i.e., of unspecified length) would simply be the sum of these numbers.        Length of permutation | Number of permutations       ----------------------------------------------           0                 |    1           1                 |    5           2                 |    5⋅4           3                 |    5⋅4⋅3           4                 |    5⋅4⋅3⋅2           5                 |    5⋅4⋅3⋅2⋅1   Of course we can express the total number of permutations of unspecified length of $n$ items as $\displaystyle\sum_{k=0}^n {}_n\text P_k$ but is there is a neater expression that this sum evaluates to, or at least a conventional notation for this number?
61581
I believe that this is a pretty simple question in terms of combinatorics.  Assuming we have the following set $\{ {1,2,3...n} \}$  In how many ways can we choose 3 subsets (A,B,C) such that the intersection between all them is empty?   $ A \cap B \cap C = \emptyset $  Well, what I have so far is the following:  For A we have $ 2^n $ options (where n is the size of the set) Then, for B, the remaining options are exactly $ 2^{n-|A|} $ since we can choose only from subsets who does not have elements in common with A. And finaly, for C, since we already have an empty intersection, we can choose whatever subset we want and get the expected result $ \emptyset $.  But for some reason it feels like the numbers are too big. If we take for example the set {1,2}, then, according to my "formula", the number of options should be:  $ \binom{4}{1} * \binom{2}{1} * \binom{2}{1} = \frac{4!}{3!} * \frac{2!}{1!} *  \frac{2!}{1!} = 16 $  Does it make sense?
97503
How many pairs $(A,B)$ of integers up to $n$ are there such that $\gcd(A,B)=B$, not counting those pairs where $B^2=A$?   If we consider $n = 5$ we have $25$ possible pairs. They are $$(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4),(2,5),\dotsc,(5,5)$$  Of them, $8$ pairs satisfy the above condition. My main objective is to find the number of such pairs if $n$ is given, with a efficient method. One of my friends showed me a method but he didn't state the reasoning behind it.  Here, I'm presenting his method for $n=10$. $$ \begin{align} &amp; 2 \cdot \left(\left(\left\lfloor\frac{10}{1}\right\rfloor - 1\right) + \left(\left\lfloor \frac{10}{2} \right\rfloor - 2\right) + \left(\left\lfloor \frac{10}{3} \right\rfloor - 3\right)\right) \\ =&amp; 2 \cdot ((10 - 1) + (5 - 2) + (3 - 3)) \\ =&amp; 2 \cdot (9 + 3 + 0) \\ =&amp; 24 \end{align} $$ Can anyone explain the reasoning behind the above method in details and clearly?
61029
Task is:  Let $A$ be a finite set and let $B$ be a subset of $A$ with $|A|=n$,$|B|=m$ and $0&lt; m &lt; n$.Find a formula for the number of subsets of $A$ that contain $B$ and prove your statement.  I assume this is $2^m$ + something. $2^m$ would count the subsets containing only elements of $B$, but i'm not sure how the sets of the form $(a_1,a_2,b_1)$ or similar would be counted. I'm having troubles with this so help would be appreciated.
52150
Is $(A \cup B)\times (C ∩ D)=(A∪C)×(B∪D)$ true for all sets A,B,C and D?  I have no idea what to do here. How could I possibly go about trying to prove this?  Or disprove it?
121362
if we choose a size $25$ subset of the set: $\{1,2,....100\}$ what is the expectancy of the number of sequential pairs in the subset? expectancy still confuses me, can anybody help?
22520
I came to point where I suppose for case 1 that $A\subseteq B$ and conclusion is trivial. For case 2 I suppose that $A\not\subseteq B$ and try to prove $B\subseteq A$, but that gets me nowhere. Any pointers here are most welcome.
117892
releasing a second question concerning ordered stuff and set theory, which is very similar to my first question () which I'm putting here for reference.  The next problem that I'm stuck at in my book is this: we have an ordered triple $(a,b,c)$ and we want to define it using set theory. Why would $\{\{ a\} ,\{ a,b\} ,\{ a,b,c\}\}$ not work? The book requires from me to prove why it is not valid.  Additional info: I don't know how this matters but I'm gonna put it up anyhow. It is written within the book that the correct way to show it is $\{\{ a\} ,\{\{ a\} ,\{\{ b\} ,\{ b,c\}\}\}\}$  EDIT: Now, I consider that the correct case should matter. Besides pointing out why the first case is wrong I'm curious as to why the second one is correct
61324
Suppose that $A, B, C$, and $D$ are sets with the cardinalities related as  $|A|=|C|$ and $|B|=|D|$. Prove that the cardinality of $A\times B$ is equal to the cardinality of $D\times C$.  I know that I must prove the bijection of the function $f: A \times B \to C \times D$, but I am not sure how to say this? Can anyone help me?
72926
Hello I am taking a Discrete Mathematics course and having some trouble with this question about sets:  Under what conditions is $A- B = B- A$  Diagram:   Diagram:   Maybe I'm understanding incorrectly, but how can A-B and B-A be equal if they contain elements that are not in each other?
41015
How many subsets of $\{1,2,...,n\}$ have no two consecutive numbers ?  Here is the solution :  The subsets are interpreted as $n$-words from the alphabet $\{0,1\}$. Let $a_n$ be the number of words with no consecutive ones. Then, a word can start from $0$ and proceed in $a_{n-1}$ ways or start with $10$ and proceed in $a_{n-2}$ ways. Therefore, $a_{n} = a_{n-1} + a_{n-2}$. $a_1 = 2, a_2 = 3$. So, $a_n = F_{n+2}$.  I have no trouble understanding the part of the argument linking $a_n$ with the Fibonacci numbers. But, I have trouble understanding the bijective argument.  What is a $n$ word ? And, how is the bijective constructed here ? How is $a_n$ linked to the question ?