Basic Enumeration
Basic Enumeration
The twelvefold way f:N→M n balls are put into m bins balls per bin: unrestricted ≤1 ≥1 n distinct balls, m distinct bins mn (m)n n identical balls, m m distinct bins n n distinct balls, 1ifn≤m m identical bins 0 ifn>m n identical balls, 1ifn≤m m identical bins 10 if n>m
balls per bin: unrestricted ≤ 1 ≥ 1 n distinct balls, m distinct bins n identical balls, m distinct bins n distinct balls, m identical bins n identical balls, m identical bins f n balls are put into m bins : N M mn (m)n m n ⇥ 1 if n m 0 if n>m 1 if n m 0 if n>m The twelvefold way
Compositions of an integer n beli k pirates How many ways to assign n beli to k pirates? each receives >1 beli kcompositon ofn(（-i） each receives >0 beli weak k-composition of n
Compositions of an integer n beli k pirates How many ways to assign n beli to k pirates? each receives ≥1 beli each receives ≥0 beli k-composition of n weak k-composition of n n 1 k 1 n + k 1 k 1
The twelvefold way f:N→M n balls are put into m bins balls per bin: unrestricted ≤1 ≥1 n distinct balls, m distinct bins mn (m)n n identical balls, m m distinct bins (a-》 n distinct balls, 1ifn≤m m identical bins 10 ifn>m n identical balls, 1ifn≤m m identical bins 10 if n>m
balls per bin: unrestricted ≤ 1 ≥ 1 n distinct balls, m distinct bins n identical balls, m distinct bins n distinct balls, m identical bins n identical balls, m identical bins f n balls are put into m bins : N M mn (m)n m n ⇥ 1 if n m 0 if n>m 1 if n m 0 if n>m The twelvefold way n 1 m 1 ⇥ n + m 1 m 1
Multisets k-combination of S k-subset of S without repetition 3-combinations of S={1,2,3,4 without repetition: {1,2,3},{1,2,4},{1,3,4},{2,3,4} with repetition: {1,1,},{1,1,2},{1,1,3},{1,1,4},{1,2,2},{1,3,3} {1,4,4},2,2,2,{2,2,3},{2,2,4},2,3,3},{2,4,4, {3,3,3},{3,3,4,3,4,4,{4,4,4
Multisets k-subset of S “k-combination of S without repetition” 3-combinations of S = { 1, 2, 3, 4 } without repetition: {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4} with repetition: {1,1,1}, {1,1,2}, {1,1,3}, {1,1,4}, {1,2,2}, {1,3,3}, {1,4,4}, {2,2,2}, {2,2,3}, {2,2,4}, {2,3,3}, {2,4,4}, {3,3,3}, {3,3,4}, {3,4,4}, {4,4,4}
Multisets multiset M on set S: m:S→N multiplicity of m(x):of repetitions of x in M k-multiset on S={1,2,...,n} m(x1)+m(x2)+·+m(xn)=km(xi)≥0 a weak n-composition of k of k-muitiscts on an n-set (》=(:)
Multisets multiset M on set S: m : S N multiplicity of x m(x): # of repetitions of x in M n k ⇥⇥ : # of k-multisets on an n-set k-multiset on S = {x1, x2,...,xn} m(x1) + m(x2) + ··· + m(xn) = k m(xi) 0 a weak n-composition of k n k ⇥⇥ = n + k 1 n 1 ⇥
The twelvefold way f:N→M n balls are put into m bins balls per bin: unrestricted ≤1 ≥1 n distinct balls, m distinct bins mn (m)n n identical balls, m distinct bins () m (a-） n distinct balls, fn≤m m identical bins 0 ifn>m n identical balls, 1ifn≤m m identical bins 10 if n>m
balls per bin: unrestricted ≤ 1 ≥ 1 n distinct balls, m distinct bins n identical balls, m distinct bins n distinct balls, m identical bins n identical balls, m identical bins f n balls are put into m bins : N M mn (m)n m n ⇥ 1 if n m 0 if n>m 1 if n m 0 if n>m The twelvefold way n 1 m 1 ⇥ m n ⇥⇥
Partitions of a set n pirates k boats P=[A1,A2,...,Ak}is a partition of S: A,卡0 A∩A)=0 A1UA2U·UAk=S
Partitions of a set n pirates k boats P = {A1, A2,...,Ak} is a partition of S: Ai = Ai Aj = A1 A2 ··· Ak = S
Partitions of a set P=[A1,A2,...,Ak}is a partition of S: A,卡0 A∩A=0 A1UA2U..UAk=S of k-partitions of an n-set "Stirling number of the second kind" B.-∑{} of partitions of an n-set k=1 “Bell number
Partitions of a set # of k-partitions of an n-set “Stirling number of the second kind” # of partitions of an n-set “Bell number” n k Bn = n k=1 n k P = {A1, A2,...,Ak} is a partition of S: Ai = Ai Aj = A1 A2 ··· Ak = S
Stirling number of the 2nd kind of k-partitions of an n-set }-{"}{-} Case.I In}is not a partition block n is in one of the blocks in a k-partition of [n-1] Case.2 In}is a partition block the remaining 1 blocks forms a (%1)-partition of [n-1]
Stirling number of the 2nd kind # of k-partitions of an n-set n k n k = k n 1 k + n 1 k 1 Case.1 Case.2 {n} is a partition block {n} is not a partition block n is in one of the k blocks in a k-partition of [n-1] the remaining k-1 blocks forms a (k-1)-partition of [n-1]