Tuples {1,2,.,m} [m=0,士，r,m1y TTNOE MATCH [mlm=m×…xm JOC SS m I(m"mr Product rule: finite sets S and T |S×T=S1·T)
Tuples mn |[m] n| = Product rule: |S ⇥ T| = |S|·|T| finite sets S and T [m] ⇥ ··· ⇥ [m] ⇤ ⇥ ⌅ n [m] n = [m] = {0, 1,...,m 1} {1, 2,...,m}
Functions count the of functions f:[ml→[m In] [m] (f(1),f(2),.,f(n)∈[m]m one-one correspondence [nl→[ml台[mm
Functions [n] [m] f : [n] [m] count the # of functions [m] n one-one correspondence [n] [m] ⇥ [m] n (f(1), f(2),...,f(n))
Functions count the of functions f:[m→[m one-one correspondence [n] [m] [ml→[ml台[m]" Bijection rule: finite sets S and T 6:S1-1T= →S=T on-to
Functions [n] [m] f : [n] [m] count the # of functions one-one correspondence [n] [m] ⇥ [m] n Bijection rule: finite sets S and T ⇤ : S 11 ⇥ onto T = |S| = |T|
Functions count the of functions f:[m→[m one-one correspondence In] [m] [ml→[ml台[m]" l[n]→[ml=l[m]|=mn "Combinatorial proof
Functions f : [n] [m] count the # of functions one-one correspondence [n] [m] ⇥ [m] n |[n] [m]| = |[m] n| = mn “Combinatorial proof.” [n] [m]
Injections count the of 1-1 functions f:[ml马[ml one-to-one correspondence [n] [m] π=(f(1),f(2),..,f(n) n-permutation::π∈[m]of distinct elements m! (m)m=m(m-1)·(m-n+1)= (m-n)！ “m lower factorial n
Injections count the # of 1-1 functions one-to-one correspondence [m] n of distinct elements = (f(1), f(2),...,f(n)) n-permutation: = m! (m n)! (m)n = m(m 1)···(m n + 1) “m lower factorial n” f : [n] 1-1 [m] [n] [m]