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}