南京大学：《组合数学》课程教学资源（课堂讲义）Pólya计数法 Pólya's theory of counting

Polya's Theory of Counting INEQUALITIES S8R t a new aspect of mathematical mechod G.POLYA G.Hardy,J.E.&G.Polyo Cambridge Mathematical Library George Polya (1887-1985)

Pólya’s Theory of Counting George Pólya (1887-1985)

Counting with Symmetry Rotation ǒh.6 0d Rotation Reflection:

Counting with Symmetry Rotation : Rotation & Reflection:

Symmetries

Symmetries

Symmetry rotation reflection configuration x [n]->[m] X (m]ln] positions colors permutation π：[n 1m on-to

Symmetry 0 1 2 3 4 5 rotation reflection configuration x : [n] ! [m] X = [m] [n] positions colors permutation ⇡ : [n] 1-1 ￾￾￾! on-to [n]

Permutation Groups group(G,）with binary operator·:G×G→G ·closure:π，o∈G→π·o∈G ·associativity::π·(o·T)=(π·o）·T 。identity:e∈G,Vπ∈G,e·T=π 。inverse:Vπ∈G,o∈G,π·o=o·π=e 0=π-1 commutative (abelian)group: π·0=0·π symmetric group S.:all permutations cyclic group Cn:rotations Dihedral group D:rotations reflections

Permutation Groups group (G, ·) with binary operator · : G ⇥ G ! G • closure: • associativity: • identity: • inverse: ⇡, ￾ 2 G ) ⇡ · ￾ 2 G ⇡ · (￾ · ⌧ )=(⇡ · ￾) · ⌧ ￾ = ⇡￾1 8⇡ 2 G, 9￾ 2 G, ⇡ · ￾ = ￾ · ⇡ = e 9e 2 G, 8⇡ 2 G, e · ⇡ = ⇡ commutative (abelian) group: ⇡ · ￾ = ￾ · ⇡ symmetric group cyclic group Dihedral group Sn Cn Dn : all permutations : rotations : rotations & reflections

Permutation Groups symmetric group S:all permutations r:列m on-to cyclic group Cn:rotations π=(012…n-1)π(i)=(i+1)modn (012…n-1)》generated by(012..n-1) Dihedral group D:rotations reflections p()=(n-1)-i generated by (012...n-1)and p

Permutation Groups symmetric group cyclic group Dihedral group Sn Cn Dn : all permutations : rotations : rotations & reflections ⇡ : [n] 1-1 ￾￾￾! on-to [n] h(012 ··· n ￾ 1)i generated by (012 ··· n ￾ 1) ⇡ = (012 ··· n ￾ 1) ⇡(i)=(i + 1) mod n generated by (012 ··· n ￾ 1) and ⇢(i)=(n ￾ 1) ￾ i ⇢

Group Action configuration x:[n][m] X (m]linl permutation π：m1m group G on-to (πox)(i)=x(π() group action o:G×X→X ·associativity:（(π·o)ox=To(oox) ·identity::eor=r

Group Action 0 1 2 3 4 5 0 1 2 3 4 5 configuration x : [n] ! [m] permutation ⇡ : [n] 1-1 ￾￾￾! on-to [n] group action X = [m] [n] group G ￾ : G ⇥ X ! X • associativity: • identity: (⇡ · ￾) ￾ x = ⇡ ￾ (￾ ￾ x) e ￾ x = x (⇡ ￾ x)(i) = x(⇡(i))

Graph Isomorphism (Gl)Problem input:two undirected graphs G and H output:G≈H? p n 6) vertices 8 7 ^b Gl is in NP,but is NOT known to be in P or NPC trivial algorithm:O(n!)time Babai-Luks'83:20(vmlogn)time Babai 2015:a quasi-polynomial time algorithm! npolylog(n)=2polylog(n)

Graph Isomorphism (GI) Problem ? • GI is in NP, but is NOT known to be in P or NPC • trivial algorithm: O(n!) time • Babai-Luks ’83: time n vertices Babai 2015: a quasi-polynomial time algorithm! npolylog(n) = 2polylog(n) 2O( pn log n) ⇠ = input: two undirected graphs G and H output: G ⇠ = H ?

String Isomorphism (SI) input:two strings x,y:[n][m] a permutation group G Sn output::x≈cy?(3o∈Gs.t.oox=y)

input: two strings a permutation group output: String Isomorphism (SI) ⇠ = ? x, y : [n] ! [m] G ✓ Sn x ⇠ =G y? (9￾ 2 G s.t. ￾ ￾ x = y)

String Isomorphism (SI) input:two strings a,y [n][m] a permutation group G Sn output:x≥cy?(3o∈Gs.t.oox=y) a graph X(V,E)is a string :() →0， 1:edge 0:no edge positions←→vertex-.pairs all permutations on V induces a permutation group on Johnson group:SCS() on vertex pairs two graphs≈iff their string versions兰sgy

String Isomorphism (SI) a graph X(V,E) is a string x : ✓V 2 ◆ ! {0, 1} all permutations on V induces a permutation group on on vertex pairs two graphs X ⇠ = Y iff their string versions x ⇠ =S(2) V y positions ⟷ vertex-pairs 1: edge 0: no edge Johnson group: input: two strings a permutation group output: x, y : [n] ! [m] G ✓ Sn x ⇠ =G y? (9￾ 2 G s.t. ￾ ￾ x = y) S(2) V ⇢ S( V 2 ) ✓V 2 ◆