Subsets [m={1,2,.,m} Power set: 2lm=sSEIn 2=2n Let f(n)=|2网 f(n)=2f(n-1) f(0)=121=1
Subsets f(n)=2f(n 1) f(0) = |2| = 1 Power set: [n] = {1, 2,...,n} 2[n] = Let f(n) = 2[n] 2n 2[n] = {S | S ✓ [n]}
Three rules Sum rule: finite disjoint sets s and T SUT=S+T Product rule: finite sets S and T S×T=S·T Bijection rule: finite sets S and T' 3o:506T→1S1=7
Three rules Product rule: |S ⇥ T| = |S|·|T| finite sets S and T Sum rule: finite disjoint sets S and T |S T| = |S| + |T| Bijection rule: finite sets S and T ⇤ : S 11 ⇥ onto T = |S| = |T|
Subsets of fixed size 2-subsets of{l,2,3}:{1,2,{1,3},{2,3} k-uniform ()=S1T= ()=1 “n choose k
Subsets of fixed size 2-subsets of { 1, 2, 3 }: {1, 2}, {1, 3}, {2, 3} S k ⇥ k-uniform = {T S | |T| = k} “n choose k” ✓n k ◆ = ✓[n] k ◆
Subsets of fixed size n(m-1)…(n-k+1) n! k k(k-1)…1 k!(n-k)！ of ordered k-subsets:n(n-1)...(n-k+1) of permutations of a k-set: k(k-1)…1
Subsets of fixed size n k ⇥ = n(n 1)···(n k + 1) k(k 1)··· 1 = n! k!(n k)! # of ordered k-subsets: n(n 1)···(n k + 1) # of permutations of a k-set: k(k 1)··· 1