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