Applications of Collections by Harvard Fat Chance

[EmbraceLife]

Applications of Collections

Video links

Bilibili

my note videos p21-24

Start problem

Experiment

• steps = 2 meat + 2 vegetables = 4
• options = 7 meat + 6 vegetables = 13
• how many unique pizzas can be counted?

Solution

• divide the whole experiment into two parts: meat and vegetables
• meat part pizzas = collection count = $(^7_2)$
  • from 7 meat toppings select 2 as a unique pizza (remove order)
• vegetable part pizzas = collection count = $(^6_2)$
  • from 6 vegetable toppings select 2 as a unique pizza (remove order)
• each meat part can combine with different vegetable parts
  • total collection count = meat part count x vegetable part count = $(^7_2) \times (^6_2)$ = 7x6/2x6x5/2 = 21x15=315
• $(^7_4) \times (^6_0)$ = 7x6x5x4/(4x3x2x1) = 35
• $(^7_3) \times (^6_1)$ = 7x6x5/(3x2x1) x 6 = 35x6
• $(^7_1) \times (^6_3)$ = 7 x 6x5x4/(3x2x1) = 35x4
• $(^7_0) \times (^6_4)$ = 1 x 6x5x4x3/(4x3x2x1) = 15
• total = 315 + 350 + 35 + 15 = 715

Another Problem

Experiment

• steps = 5 students
• full options = 15 students
• constraint
  • order is no important
  • a chair has to be appointed

Solution

• total count of 15 choose 5 collections = $(^{15}_5)$
• upon which, how many ways to appoint a chair?
  • still no worry about order
  • for each collection,
  • only pick one of the five student to be the chair = 5 choices
• 
• target count = $(^{15}_5) \times 5$ = 15x14x13x12x11/(5x4x3x2x1) x 5 = 15x13x11x7

solution 2

• first select 4 officials out of 15 students (ignore chair) = $(^{15}_4)$
• second select chair out of 11 people = 11
• total ways = $(^{15}_4) \times 11$ = 15x14x13x12 / (4x3x2x1) x 11 = 15x13x11x7
• 

Third problem

Experiment

• steps = 7 slots
• full options = 2, either E or N
• constraints
  • four Es
  • three Ns

Solution

• total sequences = $2^7$
• four Es and three Ns
  • how many ways to get 4 slots out of 7 slots to be E
    • $(^7_4)$ or $(^7_3)$ to focus on 3 Ns
  • how many ways to get remaining 3 slots be N
    • 1 as order between the 3 Ns is not important
• target count = 7x6x5x4/(4x3x2x1) = 35

Fourth Problem

How many ways to go from home to work?

Experiment

• There are many paths
• each path can be seen as a sequence of repeated two letters (right or left; N or E)
• in fact to get from home to work, all ways have to have 4 Es and 3 Ns, and of course 7 steps in total

Solution

• This is a hybrid problem = sequence (collection)
• sequence = order between N and E matters (outer part)
• collection = order inside Ns or Es does not matter (inner part)
• focus on 4 Es, worry no order = $(^7_4)$
• remaining 3 slots for 3 Ns = $(^3_3 )$ = 1
• target count = $(^7_4) \times (^3_3)$ = 35

Final problem

How many paths out of the 35 above can pass through this shop in middle?

experiment

• must passing through the shop = the first 3 steps must have 2 Es and 1 N
  • part 1: between Es and Ns, we do sequence counting
  • part 2: inside Es we do collection
• we do part 2 first
  • from 3 steps we choose 2 for E = $(^3_2)$
• we do part 1 = how many ways pass through shop
  • count of Es x count of N = $(^3_2) \times (^1_1)$ = 3x2/(2x1) = 3
• not yet finished, eventually arrive at work: how many ways from shop to work?
  • count of Es x count of N = $(^4_2) \times (^2_2)$ = 4x3/(2x1)x1 = 6
• join two parts before and after shop together
  • 3 x 6 = 18

Practices

15 students (7 boys, 8 girls), choose a committee with 4 students (2 boys, 2 girls), how many

15 students (7 boys, 8 girls), choose a committee with 4 students (not 4 boys, not 4 girls), how many

same old question in the lecture above