Functions count the of functions f:[ml→[m] one-one correspondence [n] [m] [nl→[ml台[m" Bijection rule: finite sets S and T 0:S1-1T →S1=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:[nl→[m one-one correspondence [n] [m] [ml→[m]÷[m" l[m→[mll=l[mr|=m “Combinatorial proof
Functions [n] [m] f : [n] [m] count the # of functions one-one correspondence [n] [m] ⇥ [m] n |[n] [m]| = |[m] n| = mn “Combinatorial proof
Injections count the of 1-1 functions f (nml one-to-one correspondence [n] [m] π=（f(1),f(2),.,f(n)》 n-permutation:E[m]of distinct elements (m)n=m(m-1)(m-n+1）= m! (m-n)！ “m lower factorial n
Injections [n] [m] 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]
Subsets subsets of {1,2,3 } ☑， {I,{2},3}, {1,2},{1,3},{2,3} {1,2,3} [m={1,2,..,n} Power set:2Im={SS [n]} 2=
Subsets subsets of { 1, 2, 3 }: ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} Power set: [n] = {1, 2,...,n} 2[n] = 2[n] = {S | S ✓ [n]}
Subsets [ml={1,2,..,n} Power set:2rl ={SSC [n]} 2= Combinatorial proof: A subset S [n]corresponds to a string of n bit, where bit i indicates whether ie S
Subsets Combinatorial proof: Power set: [n] = {1, 2,...,n} 2[n] = A subset S ✓ [n] corresponds to a string of n bit, where bit i indicates whether i 2 S. 2[n] = {S | S ✓ [n]}