\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{fancyhdr}
\usepackage{amssymb}
\pagestyle{fancy}
\lhead{Homework 3M}
\chead{Geoffrey Bostany}
\rhead{September 10, 2014}
\begin{document}
\begin{enumerate}
\item
\begin{enumerate}
\item $A \cap B \cap C = \emptyset \nrightarrow A \cap B = \emptyset$ \\ for example \\ $A = \{1,2,3\} B = \{1,4,5\} C = \{3,5,7\} \\ A \cap B \cap C = \emptyset$ , but $A \cap B = \{1\} \ A \cap C = \{3\} \ B \cap C = \{5\}$ \\
$\mid A \cup B \cup C \mid = \mid A \mid + \mid B \mid + \mid C \mid - \mid A \cap B \mid - \mid A \cap C \mid - \mid B \cap C \mid + \mid A \cap B \cap C \mid$
\\therefore $\mid A \cup B \cup C \mid \neq \mid A \mid + \mid B \mid + \mid C \mid$
\item if A, B, and C are pairwise disjoint then \\ $A \cap B = A \cap C = B \cap C = \emptyset \to A \cap B \cap C = \emptyset$ \\ in which case, \\ $\mid A \cup B \cup C \mid = \mid A \mid = \mid B \mid = \mid C \mid$ \\ because all possible intersections are empty
\item we can disprove this by providing a counter-example, consider the following sets \\ $A = \{1,3,5\} B = \{3,5\} C = \{1,5\}$ \\ $(A-B)-C = \emptyset$ \\ $A-(B-C) = \{1,5\} $\\ therefore, $(A-B)-C \neq A-(B-C)$
\item so first we will prove that $A=B \to A \cup B = A \cap B$ \\ $A \cup B = A \cup A = A = A \cap A = A \cap B$ \\ so $A = B \to A \cup B = A \cap B$
now we will prove that $A \cup B = A \cap B \to A = B$ \\ Let $x$ be any arbitrary but particular element of A. \\ $x \in A$ \\ $x \in A \cup B$ \\ $x \in A \cap B \\ x \in B$ \\ therefore, $\forall x \in A, x \in B \to A \subseteq B$ \\ now let $y$ be any arbitrary but partcular element of B.\\ $y \in B$ \\ $y \in A \cup B$ \\ $y \in A \cap B \\ y \in A$ \\ therefore, $\forall y \in B, y \in A \to B \subseteq A$\\ now $A \subseteq B \wedge B \subseteq A \to A = B$
\end{enumerate}
\item
\begin{enumerate}
\item $\frac{n!}{(n-k)!}$\\since the balls are distinct, you decide which balls go in which bins which is the just the permuatation.
\item $\frac{n!}{(n-k)!n!}$ \\ since all the balls are identical, you are just choosing which bins to place them in. So you do n choose k.
\end{enumerate}
\item
\begin{enumerate}
\item $\frac{15!}{9!4!}$ \\ since only 4 can be tails and the other 11 have to be heads, we are just choosing which of the 15 coin flips are tails which is 15 choose 4.
\item $\frac{15!}{9!4!}*2^{12}$ \\ if at least 3 have to be heads, then we can use 15 choose 3 to decide which ones are heads, then for the rest it doesnt matter if its heads or tails so we can multiply by all further possibilities which is $2^{12}$
\end{enumerate}
\item $\frac{25!}{23!2!}$ \\ since the last letter Z is already decided for us, we are looking for 2 letter combinations that don't already contain Z and don't repeat. So we do 25 choose 2 to get all the possible 2 letter combinations. and for each combo we choose, there is only 1 they can be ordered so that they are in alphabetical order. We also could have done the permuatation then divided by 2. this would give us the same answer.
\item So if we have $2n$ contestants and they must be paired, then we must be choosing $n$ teams. So the possibilities for picking all the teams would be\\ $\frac{(2n)!}{(2n-2)!2!}*\frac{(2n-2)!}{(2n-4)!2!}*\frac{(2n-4)!}{(2n-6)!2!}...\frac{2!}{2!}$ \\ so by simplifying, we get $\frac{(2n)!}{(2!)^{n}}$ but this implies that the order we pick the teams in matters, but it doesnt. so we have to divide out the number of possible orders to choose each team in which is $n!$\\ so correct answer is $\frac{(2n)!}{(2!)^{n}n!}$
\item $4!-3(3!)=6$ \\so there are 4 gifts with 4 different places to put them. So total combinations = 4!. But we have to eliminate different orders where each gift is in it's original slot. So
\item $\frac{16!}{2^{8}}$ \\ so if there are no contraints and he can put shoes on before socks then we get 16! total orders. But now lets say that he has to put on his first sock before his first shoe. Well that's makes us divide by 2 because half the orders will have him put shoe on first and other half will have him put on sock first. We can take this principle and apply it to all 8 feet. Therefore we divide total orders by $2^{8}$
\item $\frac{9!}{2!3!2!}$ \\ So say we just do the 9-permutations of the word. We would get $\frac{9!}{2!3!2!}$ because you have to divide out the repeating elements. But now say we take off the last letter of each distint permutation, then we get a bunch of distinct 8 element permutations. This is so because if by removing the last letter of two distinct permutations, they somehow became undistinct and repeating, they would have already been repeating even without removing the last element because the element is determined by all the others. So we are left with the answer provided.
\end{enumerate}
\end{document}
