DS1

• Set


  An unordered collection of different elements
• Relation


  The representation of the relationship between the elements of a set
• Binary Relation


  A set of ordered pairs. It may exist between objects in the same set or objects in different sets
• A binary relation from A to B is a subset of A × B
• Binary Relation Example


  • Set A = Students in school
  • Set B = Courses
  • R = Pairs of students enrolled in courses
• Domain


  Set of all FIRST members in a relation
• Range


  Set of all SECOND members in a relation
• Reflexive Relation


  A relation R on a set A is reflexive if (a, a) ∈ R for every a ∈ A
• Reflexive Relations

  • ≥, =, ≤
• Irreflexive Relation


  The opposite of Reflexive, where (a, a) ∉ R for all a
• Symmetric Relation

  A relation R on A is symmetric if (a, b) ∈ R implies (b, a) ∈ R
• Symmetric Relations

  • =
• Asymmetric Relation


  The opposite of Symmetric, where (a, b) ∈ R implies (b, a) ∉ R
• Asymmetric Relations

  • <, >
• Antisymmetric Relation

  A relation R on A is antisymmetric if (a, b) ∈ R and (b, a) ∈ R implies a = b
• Transitive Relation


  A relation R on A is transitive if (a, b) ∈ R and (b, c) ∈ R implies (a, c) ∈ R
• Partial Order Relation

  A relation R on A is a partial order if it is Reflexive, Antisymmetric, and Transitive
• Partially Ordered Set (POSET)


  The ordered pair (A, R) where R is a partial order
• Maximal Element


  An element greater than or equal to every element it is comparable to
• Greatest Element


  An element greater than or equal to every element in the set
• Total Order


  When all elements in a partial order are comparable
• Strict Partial Order

  A relation R on A is a strict partial order if it is Irreflexive, Asymmetric, and Transitive
• Strict Partial Order Example

  • Comparing numbers 1, 2, 3 where 1 < 2 and 2 < 3, but cannot compare 1 with itself
• Combining Relations

  Relations from A to B can be combined in any way two sets can be combined (union, intersection, difference, symmetric difference)
• Combinatorics is the study of arrangements of objects
• Enumeration


  Part of combinatorics that deals with counting
• Examples of Combinatorics

  • Determining telephone numbers or IP addresses
  • Enumerating possible passwords
  • Counting different orders runners can finish a race
• Sum Rule

  If a task can be performed in n1 ways and another task in n2 ways, then the tasks can be performed in n1 + n2 ways (not both)
• Sum Rule Examples

  • Choosing a fruit or cookie from 3 fruits and 2 cookies
  • Choosing a shirt or jacket from 3 jackets and 4 shirts
• Product Rule


  If a procedure has two tasks with n1 and n2 ways to accomplish each, the total ways is n1 * n2
• Sum Rule


  States that the number of ways either task 1 or task 2 can be done but strictly not both
• Sum Rule

  • Choosing a fruit or a cookie (but not both)
  • Choosing a shirt or a jacket
• Product Rule


  When we break a procedure into two tasks, with n1 ways to accomplish the first and n2 ways to accomplish the second, the product of these two numbers gives us the total ways to complete both tasks
• Product Rule

  • Making pizza combinations with 3 types of cheese, 3 types of meat, and 3 types of vegetables
• Generalized Product Rule

  If the procedure consists of sequential tasks: T1, T2, T3...Tm, it can be done by n1, n2, n3,... nm number of ways, respectively
• Generalized Product Rule

  • Awarding the top three places in a marathon with 20 runners
• The Generalized Product Rule states that if you have n tasks, each which can be performed in m ways, then the total number of ways to perform all tasks is n x m
• Permutation


  The arrangement of objects in which order is important
• Permutation with Repetition

  The order of selection matters, and the same element can be chosen multiple times. The formula is: nPr = n^r
• Permutation without Repetition

  The used value should not repeat. The formula is the same as the permutation formula