• XeLaTeX (Unicode) or LaTeX (European Languages)
• Markup Language built on TeX
• Tags: \tag
• Environments: \begin{..} ... \end{..}
• Grouping: {...}
• Math mode: $$d = \sqrt{a_0^2 + a_1^2}$$
• Spacing: \vfil \hfil \bigskip \smallskip

• Font size: \tiny \small \normalsize \large \huge
• Font families: \bf \tt \sl \it
• Document segments: \section \subsection \subsubsection
• Graphics: \includegraphics{width=\columnwidth}{pic.png}
• Tables: \begin{tabular}{lr} aa & 3.5\\ b & 17.2\\ \end{tabular}
• Footnotes: \footnote{This is a note}
• Citations: \cite{Knuth:1970}
• Cross links: \label{id} .. As seen in \ref{id}

\addresslabel[\fboxsep=5mm]{\vbox to 75mm{%
    \hbox to 40mm{\kern-5pt
      $\vcenter{\hbox to 1.7cm{%
        \includegraphics[width=1.7cm]{payap.png}\hss}}\
        \vcenter{\raggedright
          Payap University\\ Faculty of Sci\\
          Amphur Muang\\  Chiang Mai 50000\\ 
          Thailand\\}$\hss}%
    \vfill{\centering {\Large\scshape 
       \textbf{Dr.~Robert~P.~Batzinger}\\}\medskip
       \textit{Instructor Emeritus}\\}
    \vfill{\raggedleft \small
        \textit{Office: \phonei}\\%
        \textit{LinkedIn: robert-batzinger}\\%
        \textit{Email: \emaili}\\}}}

• The order of the elements is meaningless.
  Given \( A = \{1,2,3\} \) and \( B = \{2,3,1\}: \) \( A = B \)
• There are no duplicate elements in a set.
• Given \( A = {1,2,3}: \) \( {\cal P}(A) = \) \( \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} \)

Please note which of these is true

• Given \( A=\{1,2,3\}, X = {\cal P}(A): \)
  \( \qquad\exists y \in X: y \subseteq A, y = A \)
  Hint (What is the value of \( y \) ?)

• Given \( A = \emptyset, X = {\cal P}(A):X = A \)
  Hint: (What is the value of \( X \) ?)

• Given \( A = \emptyset, X = ? \)\

\[ \small\begin{array}{|c|c|c|c|c|} \hline A & |A| & {\cal P}(A) & count({\cal P}(A)) & |{\cal P}(A)| \\ \hline \emptyset & 0 & \{\emptyset\} & (1) & 1 \\ \hline \{1\} & 1 & \{\{\emptyset\},\{1\}\} & (1+1) & 2 \\ \hline \{1,2\} & 2 & \{\{\emptyset\}, \{1\}, \{2\}, \{1,2\}\} & (1+2+1) & 4 \\ \hline \{1,2,3\} & 3 & \{\{\emptyset\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\} & (1+3+3+1) & 8 \\ \hline \{1,2,3,4\} & 4 & \{\{\emptyset\}, \{1\}, \{2\}, \{3\}, \{4\}, \{1,2\}, \{1,3\}, \{1,4\}, & (1+4+6+4+1) & 16 \\ & & \{2,3\}, \{2,4\}, \{3,4\}, \{1,2,3\}, \{1,2,4\}, &&\\ & & \{1,3,4\}, \{2,3,4\}, \{1,2,3,4\}\} & & \\ \hline \{1,2,3,4,5\} & 5 & \{\{\emptyset\}, \{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, &(1+5+10+10+5+1) & 32 \\ & & \{2,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,5\}, \{4,5\}, \{1,2,3\}, & & \\ & &\{1,2,4\}, \{1,2,5\}, \{1,3,4\}, \{1,3,5\}, \{1,4,5\}, \{2,3,4\}, & & \\ & & \{2,3,5\}, \{2,4,5\}, \{3,4,5\}, \{1,2,3,4\}, \{1,3,4,5\}, & & \\ & &\{1,2,4,5\}, \{1,2,3,5\}, \{2,3,4,5\}, \{1,2,3,4,5\}\}& & \\ \hline \end{array} \]

puts <<endmsg
A:#{setA.inspect} B:#{setB.inspect} 
C:#{setC.inspect} 
B subset A:    #{setB.subset?(setA)}
A superset B:  #{setA.superset?(setB)}
A union B:     #{setA.union(setC).inspect}
A intersect C: #{setA.intersection(setC).inspect}
A intersect C: #{(setA & setC).inspect}
A intersect C?:#{setA.intersect?(setC)}
A subtract C:  #{setA.difference(setC)}
Complement(B): #{setU.subtract(setB).inspect}
Cardinality(A):#{setA.size}
4 member of C?:#{setC.include?(4)
endmsg

A:#<Set: {1, 2, 3}>  B:#<Set: {2, 3}> 
C:#<Set: {2, 3, 4}> 
B subset A:     true
A superset B:   true
A union B:      #<Set: {1, 2, 3, 4}>
A intersect C:  #<Set: {2, 3}>
A intersect C:  #<Set: {2, 3}>
A intersect C?: true
A subtract C:   #<Set: {1}>
Complement(B):  #<Set: {1, 4}>
Cardinality(A): 3
4 member of C?: true

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{venndiagram}
\usepackage{xcolor}
\begin{document}\Large
\begin{venndiagram3sets}[labelOnlyA={1},
labelOnlyB={2},labelOnlyC={3},
labelOnlyAB={4},labelOnlyAC={5},
labelOnlyBC={6},labelABC={7},
labelNotABC={8},shade=orange]
\fillACapB \fillBCapC \fillACapC
\end{venndiagram3sets}
\end{document}

• Use the Venn.tex to create a PDF that displays the following

  • \( A \cap B \cup C \)
  • \( A \cup B \cup C \)
  • \( \neg(A \cap B \cap C) \)

• Upload the diagram to the Google Classroom

Create a Venn Diagram in yEd to represent the relationships between these standard sets:

\[ \mathbb{N}, \mathbb{P}, \mathbb{Q}, \mathbb{R}, \mathbb{W}, \mathbb{Z} \]

Sets: Slide 35

1. Use Git to pull the latest copy of the Ruby source: [group.rb]
2. Run the software and verify that all 5 methods produce the same statistics for a Venn diagram.
3. Run the profiler analysis for the fastest and slowest methods.
4. Change the sample size from 2000 to 200,2000,20000, and 200000
5. Repeat the study with a sample size of 20,000 and vary the fractions of 200, 250, 333 and 500

1. Create a 3 factor Venn Diagram and include this in your Introduction with an explanation of what the numbers and regions of a Venn diagram signify.
2. Write the Introduction that includes a description and explanation of the key research question.
3. Describe the differences of the 5 counting methods in your Methodology section.
4. Describe the differences in the profiles of the fastest and slowest methods in the results section.
5. Create a graph to show the effect of sample size on the runtime and put this in your results section
6. Create a graph that shows the effect of fraction size on runtime and put this in your results section
7. In the Conclusion, summarize the key points of your findings and make a recommendation as to what is the most efficient way to determine the counts for a Venn diagram.
8. Add the Abstract and Title.
9. Submit a shared link of the PDF file to the Canvas website

Sets: Slide 40

A function is a rule that assigns each input exactly one output.

Domain is the set of all possible inputs.

Range is the set of all possible outputs.

Given the following mappings, which would qualitfy as functions?

Surjection where the elements of the domain cover the full range of value in the range.

\[ f : \{1, 2, 3, 4, 5, 6\} \Rightarrow \{a,b,c\} \]

\[ \begin{array}{|c|c|c|c|c|c|c|} \hline Original\ domain & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline Outcomes\ value & a & a & b & b & b & c \\ \hline \end{array} \]

Injection where the elements of the domain map to unique values in the range (No duplicates).

\[ f : \{1, 2, 3, 4, 5\} \Rightarrow \{a,b,c, d, e, f\} \]

\[ \begin{array}{|c|c|c|c|c|c|c|} \hline Original\ domain & 1 & 2 & 3 & 4 & 5 \\ \hline Outcomes\ value & e & c & b & d & a \\ \hline \end{array} \]

Bijection where the all elements of the domain map to unique values which cover the entire range.

\[ f : \{1, 2, 3, 4, 5, 6\} \Rightarrow \{a,b,c, d, e, f\} \]

\[ \begin{array}{|c|c|c|c|c|c|c|} \hline Original\ domain & 1 & 2 & 3 & 4 & 5 & 6\\ \hline Outcomes\ value & f & c & b & d & a & e\\ \hline \end{array} \]

• In a group of 10 people, if everyone shakes hands with everyone else exactly once, how many handshakes took place?

• If there are 10 people and 3 chairs, how many groups of 3 are possible?

• How many ways can you distribute 10 cookies to 7 students?

The additive principle states that if event \( A \) can occur in \( m \) ways, and event \( B \) can occur in \( n \) disjoint ways, then the event \( A \cup B \) can occur in \( m + n \) ways.

• For 2 sets: \( |A \cup B| = |A| + |B| - |A \cap B| \)

• For 3 sets: \( \small|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| +|A \cap B \cap C| \)

For given sets \( A \) and \( B \), the set of all ordered pairs \( \{x,y\} \) where \( x \in A \) and \( y \in B \)

\[ \hbox{For}\ A = \{1,2,3\}\ \hbox{and}\ B = \{A,B,C,D\} \]

\[ A \times B= \left\{ \begin{array}{ccc} \{1,A\} & \{2,A\} & \{3,A\}\\ \{1,B\} & \{2,B\} & \{3,B\}\\ \{1,C\} & \{2,C\} & \{3,C\}\\ \{1,D\} & \{2,D\} & \{3,D\}\\ \end{array} \right\} \]

If event \( A \) can occur in \( m \) ways, and each possibility for \( A \) allows for exactly \( n \) ways for event \( B \), then the event \( A \cup B \) can occur in \( m \times n \) ways

For sets: \( |A \times B| = |A| \cdot |B| \)

\[ \small\begin{array}{cccc} \textbf{n} & \textbf{Sequence} &\textbf{Sum} &\textbf{Equiv}\\ \hline 1 & \small 1 & 1 & 1{(1+1)\over 2} \\ 2 & \small 1+2 & 3 & 2{(1+2)\over 2} \\ 3 & \small 1+2+3 & 6 & 3{(1+3)\over 2} \\ 4 & \small 1+2+3+4 & 10 & 4{(1+4)\over 2} \\ 5 & \small 1+2+3+4+5 & 15 & 5{(1+5)\over 2} \\ 6 & \small 1+2+3+4+5+6 & 21 & 6{(1+6)\over 2} \\ 7 & \small 1+2+3+4+5+6+7 & 28 & 7{(1+7)\over 2} \\ 8 & \small 1+2+3+4+5+6+7+8 & 36 & 8{(1+8)\over 2} \\ \hline \end{array} \]

\[ \begin{array}{rcc} count & = & \sum{\{1 .. n\}} + \sum{\{1 .. (n-1)\}} + ... + \{1\} \\ & = & {x(x+1)\over 2} + {(x-1)((x-1)+1)\over 2} + ... + 1 \\ & = & {x_n + x_n^2\over 2} + {x_{n-1} + x_{n-1}^2\over 2} + ... + {x_{1} + x_{1}^2\over 2}\\ & = & {\sum_{i=1}^{n}\ x_i + \sum_{i=1}^{n}\ x_i^2\over 2} \\ \end{array} \]

If \( N \) objects are placed in \( K \) boxes, then there is at least one box containing at least \( \lceil N/K \rceil \) objects.

Example:

Among 100 people, there are at least \( \lceil 100 / 12 \rceil = 9 \) who were born in the same month.

• A drawer contains a dozen brown socks and a dozen black sock, all unmatched. A man takes socks out at random in the dark.

  • How many socks must he take out to be sure that he has at least 2 socks of the same Color?
  • How many socks must he take out to be sure that he has at least two black socks?

• If there are five possible grades (i.e., A, B, C, D, F), what is the minimum number of students needed to Ensure that at least six students get the same grade.

• A palindrome is a string that is identical to the string in reverse order. How many bit strings of length \( n \) are palindromes?

• How many licence plates can be made using either two letters followed by 4 digits or four letters followed by 2 digit is?

• How many books can be identified using the 12 digit ISBN?

• Total number of subsets:

\[ |{\cal P}(A)| = 2^5 = 32 \]

• Total number of subsets of size \( n \) :

\[ \left({|A|\over n!\ (|A| - n)!}\right) \]

\[ \small\begin{array}{|c|c|c|c|c|} \hline n=0 & n=1 & n=2 & n=3 & n=4 & n=5 \\ \hline \left({5\atop 0}\right) & \left({5\atop 1}\right) & \left({5\atop 2}\right) & \left({5\atop 3}\right) & \left({5\atop 4}\right) & \left({5\atop 5}\right) \\ \hline \left({5!\over 0!\ 5!}\right) & \left({5!\over 1!\ 4!}\right) & \left({5!\over 2!\ 3!}\right) & \left({5!\over 3!\ 2!}\right) & \left({5!\over 4!\ 1!}\right) & \left({5!\over 5!\ 0!}\right) \\ \hline {5\cdot4\cdot3\cdot2\cdot1\over (5\cdot4\cdot3\cdot2\cdot1)} & {5\cdot4\cdot3\cdot2\cdot1\over (1)(4\cdot3\cdot2\cdot1)} & {5\cdot4\cdot3\cdot2\cdot1\over (2\cdot1)(3\cdot2\cdot1)} & {5\cdot4\cdot3\cdot2\cdot1\over (3\cdot2\cdot1)(2\cdot1)} & {5\cdot4\cdot3\cdot2\cdot1\over (4\cdot3\cdot2\cdot1)(1)} & {5\cdot4\cdot3\cdot2\cdot1\over (5\cdot4\cdot3\cdot2\cdot1)} \\ \hline {1 \over 1} & {5 \over 1} & {5\cdot4 \over 2\cdot1} = {5\cdot2\over 1} & {5\cdot4\cdot3 \over 3\cdot2\cdot1} = {5\cdot 2\over 1} & {5 \over 1} & {1 \over 1}\\ \hline 1 & 5 & 10 & 10 & 5 & 1 \\ \hline \emptyset & \{1\}, & \{1,2\}, \{2,3\}, &\{1,2,3\}, \{2,3,4\}, & \{1,2,3,4\}, & \{1,2,3,4,5\}\\ & \{2\}, &\{3,4\}, \{4,5\},& \{3,4,5\}, \{1,2,4\}, & \{1,2,3,5\}, & \\ &\{3\}, & \{1,3\}, \{1,4\}, &\{2,3,5\}, \{1,2,5\}, & \{1,2,4,5\}, & \\ &\{4\}, &\{1,5\}, \{1,4\}, &\{1,3,4\}, \{1,3,5\},&\{1,3,4,5\},&\\ &\{5\} &\{2,5\}, \{1,5\} & \{1,4,5\}, \{2,4,5\} & \{2,3,4,5\} & \\ \hline 00000 & 10000, & 11000,01100, & 11100, 01110, & 11110, & 11111 \\ & 01000, & 00110, 00011, & 00111, 11010, & 11101, & \\ & 00100, & 10100, 10010, & 01101, 11001, & 11011, & \\ & 00010, & 10001, 10010, & 10110, 10101, & 10111, &\\ & 00001 & 01001, 10001 & 10011, 01011 & 01111 & \\ \hline \end{array} \]

• An \( n \) - bit string is a bit string of length n. That is, it is a string containing \( n \) symbols, each of which is a bit, either 0 or 1.
• The weight of a bit string is the number of 1’s in it.
• \( B^n \) is the set of all \( n \) - bit strings, \( B^n_k \) is the set of all \( n \) - bit strings of weight \( k \) .

\[ \small\begin{array}{|l|c|c|c|c|c|} \hline weight: & k=0 & k=1 & k=2 & k=3 & k=4 & k=5 \\ \hline B^5_k & 00000 & 10000, & 11000, 01100, & 11100, 01110, & 11110,& 11111 \\ & & 01000, & 00110, 00011, & 00111, 10110, & 11101, & \\ & & 00100, & 10100, 01010, & 01011, 10011, & 11011, & \\ & & 00010, & 00101, 10010, & 10101, 11001, & 10111, & \\ & & 00001 & 01001, 10001 & 11010, 01101 & 01111 & \\ \hline B^5_k& 1 & 5 & 10 & 10 & 5 & 1 \\ \hline \end{array} \]

• Recursively break the problem down by imposing a value of the first digit of the unknown set and solving the problem for the resulting subsets:

  \[ \{?????\}_{k=3} = 0\{????\}_{k=3} + 1\{????\}_{k=2} \]

• Once the problem has been reduced to a simple subset, the values are back substituted.

\[ \begin{array}{rcccccl} |B^5_3| & = & |B^4_3| + |B^4_2| &=& 4 + 6 & = & 10 \\ |B^4_3| & = & |B^3_3| + |B^3_2| &=& 1 + 3 & = & 4 \\ |B^4_2| & = & |B^3_2| + |B^3_1| &=& 3 + 3 & = & 6 \\ \end{array} \]

\[ \begin{array}{c} (x + y)^1 = x + y\\ (x + y)^2 = x^2 + 2xy + y^2\\ (x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3\\ (x + y)^4 = x^4 + +4x^3y + 6x^2y^2 + 4xy^3 + y^4\\ (x + y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5\\ \end{array} \]

\[ \begin{array}{c} \exists n,k: n \ge 0, 0 \le k \le n \Rightarrow\\ \left({n \atop k}\right)\\ \end{array} \]

• Read as n choose k.
• Equals \( |B^n_k| \) the number of \( n \) - bit strings of weight \( k \)
• Equals the number of subsets of size \( n \) with cardinality \( k \)
• Equals the number of lattice paths of length \( n \) with \( k \) steps to the right.
• Equals the coefficient of \( x^k y^{n−k} \) in the expansion of \( (x + y)^n \)
• Equals the number of ways to select \( k \) objects from a total of \( n \) objects

\[ \left({n \atop k}\right) =\left({n-1 \atop k-1}\right) + \left({n-1 \atop k}\right) \]