Generating Function Type of Polya Theorem (1): my notes on a 7 minute Ma Yuchun video. https://www.youtube.com/watch?v=rfV4gRLzShI
Continuing our exploration of Pólya's theorem from these notes https://www.facebook.com/cj.fearnley/posts/10224471583672751
When counting distinguishable colorings in situations involving symmetry, can we use Pólya's theorem to determine how many objects of each color there are?
For the necklace problem: how many ways are there to color a 3-bead necklace with 4 colors so that there are 2 red beads and 1 green? (see https://www.cjfearnley.com/MathCounts/MaYuchun-Combinatorics-Notes/Week8.05.ApplicationPolyaTheorem.html)
In the theory of generating functions, we learn that if there are p types of objects with nᵢ indistinguishable objects of type i, 1≤i≤p. If we can pick any number of objects of each type, then the number of distinguishable ways of picking k objects is given by the coefficient of xᵏ in the generating function (1+x+x²+⋯+xⁿ¹)(1+x+x²+⋯+xⁿ²)⋯(1+x+x²+⋯+xⁿᵖ).
So, in particular, the number of ways to pick a total of 3 beads by picking any number of red (r), yellow (y), blue (b), or green (g) beads is given by the coefficient of any combination of triplets of r, y, b, or g in the expansion of (r + y + b + g)³ = r³ + y³ + b³ + g³ + 3r²y + 3r²b + 3r²g + 3y²r + 3y²b + 3y²g + 3b²r + 3b²y + 3b²g + 3g²r + 3g²y + 3g²b + 6ryb + 6rbg + 6ryg + 6ybg
Note the video is missing two terms.
The coefficient of each term is determined by the multinomial coefficient, the permutations of r₁ 1's, r₂ 2's, ..., rₜ t's where the total number of r's total n (Σrᵢ=n), which is given by P(n;r₁,r₂,...,rₜ)=n!/r₁!⋅⋅⋅rₜ!.
multinomial theorem: (a₁+a₂+⋅⋅⋅+aₜ)^n = Σ(n!/a₁!a₂!⋅⋅⋅aₜ!)(a₁^r₁)(a₂^r₂)⋅⋅⋅(aₜ^rₜ) = ΣP(n;r₁,r₂,...,rₜ)(a₁^r₁)(a₂^r₂)⋅⋅⋅(at^rₜ)
These are further explained in these notes for Ma Yuchun's lecture on permutations of multisets https://www.cjfearnley.com/G+Posts/20161002%20-%20Permutations%20of%20Multisets_%20a%2010%20minute_.html
The solution to the question above about how many ways for 2r and 1g is the coefficient of r²g which is 3.
How many ways are there to string 3 distintly colored symmetrical beads (red r, blue b, and green g) into a 4 bead necklace?
We analyze as before with Pólya's theorem but track each kind of bead using the appropriate generating functions:
We have 2 ±90° rotations with 1 4-cycle, so 2 (4)¹ whose generating function is 2(r⁴+b⁴+g⁴).
We have 1 180° rotation with 2 2-cycles, so 1 (2)² whose generating function is (r²+b²+g²)².
We have 1 identity permutation with 1 1-cycle, so 1 (1)⁴ whose generating function is (r+b+g)⁴
Flipping in axis 1 (cutting symmetrically between pairs of beads): there are two such reflections with 2 2-cycles: so 2 (2)² whose generating function is 2(r²+b²+g²)²
Flipping in axis 2 (cutting two beads in half): there are two such reflections with 1 2-cycle and 2 1-cycles: so 2 (2)¹(1)² whose generating function is 2(r+b+g)²(r²+b²+g²)
As before there are, in total, 8 permutations. Pólya's theorem gives ⅛(2*3¹+1*3²+1*3⁴+2*3²+2*3³)=21.
The generating function for choosing a total of 3 beads by picking any number of red (r), blue (b), or green (g) beads is given by (r + b + g)³ = r³ + b³ + g³ + 3r²b + 3r²g + 3b²r + 3b²g + 3g²r + 3g²b + 6rbg.
Recall Pólya's Theorem: If the permutation group G̅={p̅₁,…p̅ₕ} where each p̅ᵢ 1≤i≤h is a permutation of n objects colored with m colors. Let C(p̅ᵢ) be the number of cycles in p̅ᵢ (in disjoint cycle form). Then l=(1/|G|)Σm^{C(p̅ᵢ)} where 1≤i≤h and l is the number of distinguishable classes of indistinguishable symmetries.
The weighted form of Pólya's theorem is P(G)=(1/|G̅|)Σ_{j=1}^hΠ_{k=1}^nSₖ^(C(p̅ⱼ)
where we have replaced the m^{C(p̅ᵢ) with generating functions Sₖ=b₁ᵏ+b₂ᵏ+⋯+bₘᵏ for 1≤k≤n and the selection of the m colors is chosen by b₁ of type 1, b₂ of type 2, …, bₘ of type m.
Subtitles: https://www.cjfearnley.com/TsinghuaX60240013.x/week8/8-3-1-en.srt
From the free on-line course: https://www.edx.org/course/combinatorial-mathematics-2
Lecture: Week 8, Generating Function Type of Polya Theorem, Generating Function Type of Polya Theorem (1)