More on multiplication principle by Harvard Fat Chance

[EmbraceLife]

More on multiplication with factorial

keywords

factorial, multiplication

Video links

Bilibili videos my notes part 1-3 p10-12

start problem

Experiment analysis

• total steps = 15 (count down to 1)
• full options for all steps are the same = 15
• count = 15 x 14x 13 x ... x 15 - (15-1) = 15!

Factorial is very convenient and simple expression than line them up

n x (n-1) x (n-2) x (n-3) x ... x n - (k-1) = $\frac{n!}{(n-k)!}$ why? (count down k numbers)

• n x (n - 1) x (n-2) x (n-3) x ... x 1 = n!
• n x (n - 1) x (n-2) x (n-3) x ... x [n-(k-1)] x (n - k) x ... x 1 = n!
• to remove (n - k) x ... x 1 from n!
• (n - k) x (n - k - 1) x ... x 2 x 1 = (n-k)!
  • because it is continous sequence multiplication like 1x2x3...xn = n!

three digit numbers example

3-digit number experiment

• constraint
  • 0 is excluded for all three digits
  • full option for all digits (all steps) = count (1,2,3,..., 9) = 9
  • no repetition = decreasing options
• steps = 3 digits = 3
• options are decreasing from 9
• count = 9 x 8 x 7 = $\frac{9!}{(9-3)!}$ = 504

count odd numbers from above example

added constraint

• select only odd numbers from the 504 numbers above
• odd number = numbers ending with 1,3,5,7,9

experiment analysis

• total steps = 3 digits = 3
• count from first digit or from last digit both are valid
• with only the last step has 5 option numbers to choose
• but we start with first two digits, the last digit may not have 5 options, so the last step's option become variable which is bad!!

solution

• the last digit has the most contraint, start with it
• count = $opt_{step3} \times opt_{step2} \times opt_{step1} = 5 \times (9-1) \times (9-1-1) = 5 \times 8 \times 7$

more challenge problem with no two boys together

constraint

• since 8 boys and 7 girls, boys and girls must cross sit to avoid any two boys sit together
• boy(8) x girl(7) x boy(8-1) x girl(7-1) x boy(8-2) x girl(7-2) x ...boy(1) x girl(1)

problem (insights for using formula)

• we can't apply factorial to the count expression above
• but if we take out boys and girls into two groups, we can apply factorial
• we can apply multiplication rule above, but not use factorial :atom_symbol:

solution

• boys group = 8 x 7 x 6 x ... x 1 = 8!
• 
• girls group = 7 x 6 x ... x 1 = 7!
• 
• put together = 8! x 7!

Practice

constraints

• we start from the most constraints to the least

• last digit options = 1,3,5,7,9

• first digit options = not 0, not last digit = 10-1-1

• second digit options = 10-1-1-1

[Enemy-77]

英文版的第12个视频，也就是这个栏目的最后一个例子“三位数，无重复数字，奇数”。讲解听明白了。但是：最后一位有5种可能，接着看倒数第二位，则有9种可能，第一位排除0和后两位出现的数字就是7种可能，那么就是798，和视频中不一样，不知道我是哪里想错了？

[EmbraceLife]

对比我的笔记视频看看，相关细节应该都有讲到；如果还是有疑问，把英文和中文视频中出现疑问的时间点（如果中文视频也没有解决你的疑问）标注清楚，同时告诉我为什么中文视频没有解决你的疑惑；我会尝试回答