search

EmbraceLife / shendusuipian

To know stats by heart
287 stars 70 forks source link

Counting Collections by Harvard Fat Chance #23

Open EmbraceLife opened 6 years ago

EmbraceLife commented 6 years ago

Counting Collections

Keywords

sequences, collections

Video links

Bilibili

my notes videos p17-19

Key questions

how to count sequences (a group of ordered numbers)?

how to count collections (a group of unordered numbers)?

Interesting points

Start problem

Analysze the Experiment

  • steps = 5 students
  • full options = 15 students
  • constraint = choose a collection (not a sequence)

Solution

  • to choose a sequence (ordered numbers), we first all the unique groups of numbers (unordered, collections), then who is which title matters (give an order)
    • 15x14x13x12x11
    • $\frac{15!}{(15-5)!}$ = A
  • but to choose a collection, we only need to focus on all the unique groups of numbers(unordered, collections), who is which title does not matter
    • so to count such a collection, we need to undo order step
    • N = collection count
    • each collection has 5 students, unordered, anyone can be any title
    • to give order to such a collection = 5 students take 5 titles = 5!
  • collection count x count ordered of a single collection = sequence count
    • collection count = sequence count / ordered count = A / 5!
    • $\frac{n!}{(n-k)!k!}$, k = steps, n = full options

Example to apply

Analyze the experiment

  • steps = 3 distinct toppings
  • full options = 6 toppings to choose from
  • sequence = 3 distinct toppings and their order matters
  • collection = 3 distinct toppings and their order does not matter

Approahces

  • sequence = 6x5x4
  • collection = sequence / order count
  • order count = 3!
  • target count = $\frac{6!}{(6-3!)3!}$

Binomial coefficient

why such a name for later videos

$(^n _k) = \frac{n!}{(n-k)!k!}$

but how do you know it is a whole number?

  • because it can be achieved as N x k! = $(^n _k)$

properties of Binomial Coefficient

$(^nk) = \frac{n!}{(n-k)!k!} = \frac{n!}{(n-(n-k))!(n-k)!} = (^n {n-k})$

recursion

$(^n_k) = (^{n-1}k) + (^{n-1}{k-1})$

  • complementary = with A or without A
  • take an Ace red Heart for example
  • $(^{52}_4)$ = 52 cards take 4 cards out and remove the ordered count
  • $(^{51}_4)$ = if Ace red heart will not be selected (taken red heart Ace out), then from 51 cards select 4 cards without ordered count
  • $(^{51}_3)$ = if Ace red heart will be selected, then from 51 cards, select the remaining 3 cards
  • $(^{52}_4) = (^{51}_4) + (^{51}_3)$

practice

15 questions (8 TF questions, 7 multiple-choice questions) choose 5 questions, but at least 1 TF and at least 1 multi-choice, how many choices do we have?

Analyse the experiment

  • steps = 5 questions
  • full options = 15 questions
  • constraints
    • at least 1 TF and at least 1 multi-choice
    • it is about collection count (order count should be removed)

Approaches

  • total count on collection = $(^{15} _5)$
  • constraint on two at least is too tedious to confront directly
  • complementary = no TF question, no multiple choice question
  • collection count (5 questions have no TF question) = $(^7_5)$
  • collection count (5 questions have no multi-choice question) = $(^8_5)$
  • the above two collection counts have no overlapping
  • so, target count = total - complemtary count = $(^{15}_5) - (^8_5) - (^7_5)$