Basic Enumeration
Basic Enumeration
Enumeration (counting) Sample questions: How many character strings of length n? How many trees of n vertices? How many ways of returning homeworks to n students so that no one receives his/her own homework. How many ways to change n yuan? f(n)=Sn
Enumeration (counting) • How many character strings of length ? • How many trees of vertices? • How many ways of returning homeworks to students so that no one receives his/her own homework. • How many ways to change yuan? Sample questions: n n n n n f(n) = |Sn|
Tuples {1,2,,m} [m]=9,1,m-1} TTNOE MATCH [mn=m×…×m JO C SS m Im=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 [n] [m] (f(1),f(2),.,f(n)∈[m]n one-one correspondence [ml→[ml今[m
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:[nl→[m one-one correspondence [n] [m] [nl→[ml台[mln Bijection rule: finite sets S and T 0: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|