MDM4U – Grade 12 Data Management – Combinations Test

Grade 12 – Data Management – Combinations

Venn Diagrams

  • Venn Diagrams: a number of overlapping circles each represent their own properties. Overlapped areas show values which share both properties. Center where all circles overlap show values which share all properties
  • Venn Diagrams placed in a rectangle have “s” to denote the universal set
  • Operations on Venn Diagrams
    • n(A): number of values with property A
    • n(A U B): number of values with property A or B (Union)
    • n(A n B): number of values with only A and B (Intersection)
  • Principle of Inclusion and Exclusion

n(A U B ) = n(A) + n(B) – n(A n B)

n(B U C U P) = n(B) + n(C) + n(P) – n(B U C) – n(B n P) – n(C n P) + n(B n C n P)

Combinations

  • Combination: a combination of n distinct objects taken r at a time is a selection of r of the n objects without regard to order.
    • Denoted as: C(n,r) or (n r) or nCr or “n choose r”

 

C(n,r) = n! / [(n-r)!*r!]

where n, r E W, n >= r

 

  • If some elements are alike and if atleast one item is to be chosen, then the total number of selections from P alike items, Q alike items, R alike items and so on is:

 

(P+1)(Q+1)(R+1).. -1

 

  • Each way P, Q, or R can be chosen is added by 1 for the possibility that it isn’t chosen
  • 1 is subtracted for the possibility where all aren’t chosen

 

Pascal’s Triangle

  • Properties of Pascal’s Triangle
    • it’s symmetrical
    • potentially infinite in size
    • each number is the sum of the 2 numbers above it to the left and right
    • Combinations in the form C(row number, element number) also form Pascal’s Triangle

 

Pascal’s Identity: (n , r) = (n-1 , r-1) + (n-1 , r)

Row n: nC0*nC1*nC2*nC3*nC4… nCn

Sum of nth row: 2n