南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Basic Enumeration

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]