Math 880

MSU MATHEMATICS

MTH 880
Graduate Combinatorics

Fall 2025

Instructor: Prof. Peter Magyar , magyarp@msu.edu,
Lecture: Mon, Wed, Fri 11:30−12:20pm in Wells C-514cycle
Drop-In Office hours: Mon, Wed, Fri 12:30-2:00pm in Wells D-326 and Zoom
Call 353-6330 anytime to see if I am in.
Course Information: Grading and homework policies, administrative dates.
Announcements
- Homework 4 due Fri 10/10
Homework: Usually due Mon. You should discuss homework with other students, but you must write out solutions in your own words. LaTeX is encouraged. Use computational tools like Wolfram Alpha, Mathematica, or the like whenever helpful. Please do not look up answers to specific problems, including with AI; but if you do get help from an outside source, give explicit credit. Click ⊞ to open sections.
- ⊞ HW Style Guide
  - Write short. Give all needed information in minimum words.
  - Write neat. LaTeX is encouraged, but not required.
  - Adapt to your audience. Omit details obvious to them, expand arguments unfamiliar to them. In your homework, consider your audience as other students in our course who have not done this problem.
  - Give the setup. At the beginning of each problem or section, state what it is about. Always state the Proposition before a proof. Do not assume the reader knows what you are talking about: you yourself will have forgotten when reviewing.
- Homework 1 Wed 9/3 (tex)
- Homework 2 due Mon 9/15 (tex)
- Homework 3 due Wed 10/1 (tex)
- Homework 4 due Fri 10/10 (tex)
Notes
- ⊞ Textbooks free online
  - [St] Stanley, Enumerative Combinatorics. Two-volume main text.
    - Volume I, 2nd ed, Ch 1−4, from author. Page numbers differ in online vs printed versions. I will refer to section numbers.
    - Volume II, Ch 5−7, from MSU Library.
  - [FS] Flajolet & Sedgewick, Analytic Combinatorics. Supplementary text, from author.
  - [HHM] Harris, Hirst, Mossinghoff, Combinatorics and graph theory, 2nd ed. Undergrad background, from Springer.
  - [W] Herbert Wilf, Generatingfunctionology. Undergrad background, from author.
  - [Stanton-White] Stanton & White, Constructive Combinatorics. Interesting material about bijections and involutions, from Springer.
  - [Kerber] A. Kerber, Applied Finite Group Actions, 2nd ed. Detailed study of the Polya-Redfield method, from Springer.
  - Doubilet, Rota, Stanley, The Idea of Generating Function. Expanded version of [St] §3.18-19, from Euclid or here.
- Math 481, 482. Undergrad course pages, with HW and notes.
- Computer algebra: Wolfram Alpha online, Mathematica free at MSU Tech Store.
- 8/25 Method of generating functions for binomial coefficients ⊞ Notes
  - Reading: [St] §1.1.1−1.1.5, 1.1.12, 1.1.17, 1.2; [FS] pp. 16, 19, 23.
    [HHM] pp. 131−133, 138−140, 164−165. Math 481 Notes 1/13, 1/22, 2/3.
  - Graded class 𝒜 of all S ⊂ [n], Multiplicity Transform to {0,1}ⁿ
  - Generating function A(x) = (1+x)ⁿ, Taylor coefficient formula (n | k) = n^k/k!
  - Deletion Transform & Pascal Triangle.
  - HW: Do ((n | k)) = n-multichoose-k similarly.
- 8/27 Method of generating functions for Fibonacci numbers, Twelvefold Way ⊞ Notes
  - ℬ = Seq 𝒜 ⇒ B(x) = ¹⁄_(1−A(x))
  - Fibonacci combinatorial class: F(x)/x = ∑ F_k+1x^k = ¹⁄_{(1−(x+x²))} , ℱ = Seq{1,2} hopscotch boards.
  - Twelvefold Way: Functions, balls & baskets, dist & indist;
  - Table entries: (1) n^k, (2) n^k, (3) surj(k,n); (4) ((n | k)) = (n multi-choose k), (5) (n | k) = (n choose k), (6) ((n | k−n))
  - Reading: [St] §1.9. Math 482 HW 1/8 & 1/10. Notes 2/14: Fibonacci numbers.
  - Gen fun F(x) = ^x⁄_{(1−x−x²)}, partial fraction expansion, Binet Formula, asymptotic.
- 8/29: Generating Function Diagram. Reading: [FS] §I.1, I.2. Math 481 Generating Function Toolkit. ⊞ Notes
  - Quotient Principle for free G-action: # ^𝒜⁄_G = ^#𝒜⁄_#G; (n | k) = ^{n^k}⁄_k!, {k | n} = ^surj(k,n)⁄_n!, but ((n | k)) ≠ ^{n^k}⁄_k!.
  - Principle of Inclusion-Exclusion: [St] §2.1. Math 481 HW 1/25−1/29, Notes 1/27.
    surj(n,k) = kⁿ − (n | 1)(k−1)ⁿ + (n | 2)(k−2)ⁿ − ··· + (−1)ⁿ⁻¹(n | n−1)1ⁿ.
- 9/3 & 5: Number partitions, transforms. Reading: [St] §1.8. [FS] §I.3. Wikipedia on partitions. ⊞ Notes
  - Notations: λ = (λ₁ ≥ ··· ≥ λ_ℓ > 0) ↔ 1^m₁ 2^m₂ 3^m₃···
  - size |λ| = λ₁ + λ₂ + ··· = m₁ + 2m₂ + 3m₃ + ··· ; length ℓ(λ) = ℓ = m₁ + m₂ + m₃ + ···
  - Young diagram T = T_λ, transpose partition λ' : bijection {λ with ℓ ≤ n parts} ↔ {λ with largest part λ₁ ≤ n}
  - p_≤n(k) = #{λ with |λ| = k, length ℓ ≤ n}, generating function P⁽ⁿ⁾(x) = ∏ⁿ_i=1 ¹⁄_(1−xⁱ).
    Partition function p(k) = p_≤k(k) = #{λ with |λ| = k}, generating function P(x) = ∏_i≥1 ¹⁄_(1−xⁱ)
  - Dedekind modular function η(τ) = exp(^2πiτ⁄₂₄) P(e^2πiτ).
  - Hardy-Ramanujan circle method: p(k) ∼ ¹⁄_4k√3 exp(^π√(2k)⁄_√3).
- 9/8: Involution Principle. Reading: Wikipedia, [St] §2.6, up to Eq (2.31). [Stanton-White], Ch 4, p. 110.
  Euler Pentagonal Number Theorem, Franklin's involution.
- 9/10 Stirling partition {k | n} and Stirling cycle [k | n]
  Reading: [St] §1.9 #3, Math 481 Notes 1/27, Generating functions & Stirling numbers ⊞ Notes
  - Stirling numbers {k | n} are change-of-basis coeffs in ℂ[x] from the natural basis {x^k}_k≥0 to the falling powers {x^k}_k≥0 :
    x^k = ∑^k_ℓ=1 {k | ℓ} x^ℓ.
    Sufficient to prove for integers x = n ≥ 0. Intuitively: a function f : [k] → [n] factors into a surjective function and an injective function, uniquely up to a permutation of Im(f). Formally, the left side n^k counts all functions f, and on the right side {k | ℓ} n^ℓ counts pairs ({S₁, . . . , S_ℓ}, f), where {S₁, . . . , S_ℓ} is a set partition of [k], indexed so that min S₁ < ··· ≤ min S_ℓ; and f : [ℓ] → [n] is an injective function. Bijection takes f to S_i = f⁻¹(j) for j ∈ Im(f), and f(i) = f(S_i).
  - The inverse change-of-basis formula is:
    x^k = ∑^k_ℓ=1 (−1)^k−ℓ [k | ℓ] x^ℓ.
    Prove for integer x = n ≥ 0 by a sign-reversing involution which cancels most terms on the right side, leaving only those on the left. Since [k | ℓ] counts permutations w ∈ 𝕊_k having ℓ disjoint cycles, the right side [k | ℓ] n^ℓ represents pairs (w, f), for permutations w ∈ 𝕊_k and functions f : [k] → [n] which are constant on each cycle of w, so that f(w(i)) = f(i) for all i. Define sgn(w, f) = sgn(w) = (−1)^k−ℓ. The Cycle-Splicing Involution takes (w, f) to (w·(i,j), f), where (i,j) ∈ 𝕊_k is the lexicographically smallest transposition such that f(i) = f(j). This is clearly its own inverse, and since w ↦ w·(i,j) either splices the cycles containing i and j together or splits them apart, it always changes sign. The involution is undefined (fixed) only when f is injective, which can only happen for w = id, so the uncanceled fixed (w, f) = (id, f) are counted by n^k on the left side.
- 9/12: Catalan numbers, determinants, reflection involutions ⊞ Notes
  Catalan numbers C_k
  - Reading: 481 Notes, Catalan models. [St] §6.2, vol II p. 168; §1.5 p. 42. [FS] §I.2 p. 34-36.
  - Dyck paths from (0,0) to (2k,0) with y ≥ 0: steps (ε₁, . . . , ε_2k) with ε_i = ±1, y = ε₁ + ··· + ε_i ≥ 0 for all i, and ε₁ + ··· + ε_2k = 0.
  - Delete stilt edges around first return to y = 0 ⇒ recurrence C_k = ∑_{i+j
    = k−1} C_iC_j
    ⇒ C(x) = ^{(1−√1−4x)}⁄_2x ⇒ C(x) = 1 + x C(x)² ⇒ C_k = ¹⁄_(k+1) (2k | k)
  - C_k = (2k | k) − (2k | k−1). Proof by involution: 𝒫⁺ = {all paths ε from (0,0) to (2k, 0)}, 𝒫⁻ = {all paths ε from (0,0) to (2k, −2)}. Reflection Involution takes (ε₁, . . . , ε_2k) to (ε₁, . . . , ε_i, −ε_i+1, . . . , −ε_2k) for min i with ε₁ + ··· + ε_i = −1. Only Dyck paths are fixed, uncanceled.
  Lindstrom-Gessel-Viennot determinants
  - Reading: [St] §2.7 Determinants, Lindstrom-Gessel-Viennot Lemma.
  - Oriented graph with no oriented cycles, inscribed in a planar disk, sources s₁, . . . , s_n on left boundary, facing sinks t₁, . . . , t_n on right boundary, n × n matrix
    M = (p_ij)_n×n with p_ij = # of oriented paths from s_i to t_j
  - Theorem: det(M) = # of n-tuples of non-intersecting paths (P₁, . . . , P_n) with P_i from s_i to t_i.
  - Proof by involution. The determinant is the signed count of the class of n-tuples of paths (P₁, . . . , P_n), with P_i from s_i to t_w(i) for some w ∈ 𝕊_n, with sign = sgn(w). Reflection Involution: for the first path P_i having an intersection, let its first intersection be with P_j; keep paths P'_i & P'_j the same as P_i & P_j until the intersection, then switch them so that P'_i takes s_i to t_w(j) and P'_i takes s_j to t_w(i) . The only uncanceled (fixed) n-tuples are the non-intersecting ones, which topologically can only occur for w = id.
  - The theorem applies to much more general matrices M = (wt_ij)_n×n. We weight each edge e with a variable x_e , so path P = (e₁, . . . , e_ℓ) has a monomial weight wt(P) = x_e₁···x_{e_ℓ}. Let wt_ij be the sum of wt(P) for of all paths P from s_i to t_j . Then the determinant becomes:
    det(M) = ∑ wt(P₁) · · · wt(P_n)
    summed over all non-intersecting n-tuples of paths (P₁, . . . , P_n).
- 9/15: Tree counting. Reading: [FS] §I.5, p 64. Dlog method. 481 on rooted trees. 482 Notes 3/10 on rooted trees. ⊞ Notes
  - Tree T: a connected acyclic simple graph on vertex set V = [k]. T has k−1 undirected edges.
  - Family trees: rooted unlabeled planar trees c_k
    - One vertex is distinguished as the root or ancestor, drawn at the top, with generations of descendants drawn below.
    - Vertices are unlabeled dots, i.e. modulo relabeling by permutations in 𝒮_k
    - Planar means the descendants of each vertex are put in (birth) order, with a permutation possibly giving a different tree.
    - 𝒞 = graded class of all rooted unlabeled planar trees, counting sequence c_k = #𝒞_k, generating function c(x)
    - Deletion of the root gives the recurrence:
      𝒞 = {•} × Seq(𝒞).
      Here Seq(𝒞) means the class of sequences of trees in 𝒞, graded by the sum of the individual tree sizes.
      c(x) = ^x⁄_(1−c(x)) ⇒ c(x) = ¹⁄₂(1 − √(1-4x)).
      This is x times the Catalan generating function, so c_k = C_k−1.
    - Explanation: Instead of deleting the root vertex, delete the edge connecting the ancestor to the eldest child. This splits the tree into smaller left and right trees, obtaining the Catalan recurrence (slightly shifted).
  - Rooted unlabeled trees r_k
    - Like the previous family trees, but descendants of each vertex are unordered, forming a multiset.
    - ℛ = graded class of all rooted unlabeled planar trees, counting sequence r_k , generating function R(x)
    - Deletion of the root gives the recurrence:
      ℛ = {•} × MSet(ℛ).
      Here MSet(ℛ) means the graded class of multisets of trees in ℛ, with total size equal to the sum of the individual tree sizes.
      R(x) = ∑_k≥0 r_kx^k = x ∏_{i ≥ 1} ¹⁄_{(1−xⁱ)^r_i} .
    - The Dlog method (logarithmic differentiation) rearranges the above equation into a manageable recurrence, which is pretty much the best we can do to compute r_k:
      r_k+1 = ∑^k_n=1 ∑_{j | n} j r_j r_k−n+1 .
- 9/17 & 19: Cayley trees T_k = k^k−2. Reading: [FS] §II.5, p 125. Math 481 Graph Notes II ⊞ Notes
  - Here the vertices are labeled V = [k], with no further structure. These are just ways to choose k−1 edges connecting the k vertices.
  - 𝒯 = graded class of all labeled trees, counting sequence T_k, generating function T(x)
  - Deletion of vertex 1 gives a set of trees on a set partition of the remaining vertices [k]\[1]. We will see next week how to handle such labeled recurrences.
  - Direct counting algorithm: draw each type of unlabeled, unrooted tree T, and compute the number of inequivalent ways to label it with V = [k]. Two labelings give the same graph if related by a graph symmetry, so the number of distinct labelings is ^k!⁄_#G , where G = Sym(T).
    Result: T₂ = 1, T₃ = 3, T₄ = 16, T₅ = 125.
  - Cayley's Theorem: T_k = k^k−2.
  - Joyal bijection
    - A vertebrate is a labeled tree T endowed with distinguished head and tail vertices (which might be the same); these define a backbone, the unique path in T from head to tail. The number of vertebrates is clearly k² T_k.
    - To prove Cayley's Theorem, we give a bijection between vertebrates and all functions f : [k] → [k], which are counted by k^k.
    - A function f is equivalent to its function graph, the directed graph on V = [k] with edges i→f(i).
    - Lemma: A directed graph is a function graph if and only if it consists of disjoint directed cycles with each vertex having a directed tree appended to it, so that each tree edge is directed toward the cycle vertex as its root. For example, a permutation f ∈ 𝒮_k is a union of directed cycles only, with no extra tree vertices (roots only).
    - The bijection decomposes a vertebrate into its backbone (b₁, . . . , b_n) plus a tree appended at each backbone vertex, whose edges can be oriented toward the backbone vertex. Consider the backbone as a permutation of the set {b₁, . . . , b_n} put into increasing order. Writing this permutation in cycle notation rearranges the backbone vertices into a disjoint union of directed cycles. Reattaching the directed tree to each backbone vertex gives a function graph.
    - Inversely, each function graph defines a permutation of its cycle vertices, which can be rewritten in sequence form to define the backbone of a vertebrate. The appended trees are preserved.
  - Prufer bijection: Math 481 HW 3/25
    - This is a direct bijection from labeled trees on V = [k] to sequences a = (a₁, . . . , a_k−2) with a_i ∈ V. The bijection mapping algorithm successively deletes leaves of T, vertices ℓ having only one neighbor vertex.
    - Algorithm: Let T₁ = T, ℓ₁ = min(leaves of T₁), the numerically smallest leaf; and record its unique neighbor a₁. Remove the leaf, setting T₂ = T₁ \ {ℓ₁}, and repeat the above for T₂, ℓ₂, a₂. Iterate to obtain a = (a₁, . . . , a_k−2), and discard the remaining edge T_k−1.
    - Amazingly, no information is lost in the above mapping, and it can be inverted. Given a = (a₁, . . . , a_k−2), the leaves of T are precisely the vertices which do not appear in a. Thus define V₁ = V and ℓ₁ = min(V₁ \ {a₁, . . . , a_k−2}), and record the edge a₁−−ℓ₁. Now repeat for V₂ = V₁ \ {ℓ₁} and ℓ₂ = min(V₂ \ {a₂, . . . , a_k−2}. Iterate until V_k−1 = {u, v}, and record the final edge u−−v
- 9/19: Unlabeled trees t_k. Reading: 482 Notes 3/12 on Otter's Theorem, Otter (1948). ⊞ Notes
  - Again we consider trees on k unlabeled dots, graph-isomorphism classes of trees on V = [k] mod 𝒮_k. These are the hardest to count because they lack a useful deletion transform.
  - Otter found a formula for t_k in terms of the much easier r_k, the rooted unlabeled trees.
  - Quotient trees: Given a tree T with vertices V = [k] and edges E, having symmetry group G ⊂ 𝒮, define the quotient graph T with vertices V = V/G and edges
    E = E_NS/G where E_NS = {e = uv with u ≠ v}.
    That is, the non-symmetry edge set E_NS excludes edges which are flipped over by a symmetry, so that E has no loop edges.
    Lemma: T is a tree, so that #E = #V − 1.
  - Otter's Theorem:
    t_k = r_k − ¹⁄₂(∑_i+j=k r_ir_j − r_k/2),
    or in terms of generating functions: T(x) = R(x) − ½(R(x)² − R(x²)).
  - Proof: For a given unlabeled tree T, the number of distinct rooted trees corresponding to T is #V, and the number of distinct edge-rooted trees (having a distinguished non-symmetry edge) is #E = #V − 1. Thus:
    t_k = ∑_T 1 = ∑_T #V_T − ∑_T #E_T = r_k − e_k ,
    where r_k is the number of rooted trees, and e_k is the number of edge-rooted trees.
    Finally, edge-rooted trees, after deleting the distinguished edge, are in bijection with sets of two distinct vertex rooted trees (distinct because the distinguished edge is not allowed to be a symmetry edge). This means:
    e_k = ¹⁄₂(∑_i+j=k r_ir_j − r_k/2).
    (The last term removes the multisets of two identical trees: of course r_k/2 = 0 if k is not even.)
  - Centroids: Every tree T has a special vertex or edge called the Otter centroid. A vertex is a centroid if removing it splits T into sub-trees each with less than k/2 vertices; an edge is a centroid if removing it splits T into two subtrees each with k/2 vertices.
    Centroid Lemma: A tree has a unique centroid, either a vertex or an edge.
  - Recursively generate non-isomorphic unlabeled trees. Naive algorithm: list all rooted trees and forget the root, then eliminate isomorphic trees: difficult to check isomorphism. Get a better algorithm based on the Centroid Lemma.
    - First generate all non-isomorphic rooted trees of size at most k/2 via the recurrence ℛ = {•} × MSet(ℛ), connecting a root to all multisets of smaller rooted trees which produce the desired size.
    - To generate non-isomorphic trees of size k, consider that every tree corresponds to a unique rooted tree with root at the centroid vertex or the centroid edge. Generate these distinguished rooted trees by connecting the root to multisets of rooted trees only of size less than k/2 which produce the correct total size k; and also connect an edge between each multiset pair of rooted trees of size k/2.
  - Involution proof of t_k = r_k − e_k
    - We define a unique distinguished vertex for any tree T. (a) If T has a centroid vertex, let that be distinguished. (b) If T has a non-symmetry centroid edge connecting rooted subtrees T₁ and T₂, choose a standard order for rooted trees, and distinguish the root of the smaller subtree. (c) If T has centroid edge which is a symmetry edge, distinguish either vertex of this edge, since both make isomorphic rooted trees.
    - For every tree, we orient every edge toward the distinguished vertex.
    - Define a signed class 𝒜⁺ = rooted trees, and 𝒜⁻ = edge-rooted trees, so that #𝒜⁺ = r_k and #𝒜⁺ = e_k.
    - Define an involution I by taking an edge-rooted (negative) tree with oriented root e = u→v to the identical positive tree rooted at the vertex u (which is never the distinguished vertex). Also take any positive tree rooted at a non-distinguished vertex u to the negative tree rooted at the unique edge downstream from u. The fixed points are precisely the positive trees rooted at the distinguished vertex, which are in bijection with unrooted trees.
- 9/22: Labeled classes 𝒜˜, exponential generating function A˜(x) = ∑_k≥0 A_k ^{x^k}⁄_k!.
  Reading: [FS] §II.3 p 106. [W] §3.6 p 83. [HHM] §2.8.3, pp 231. ⊞ Notes
  Labeled constructions:
  - Labeled product 𝒜˜ ∗ ℬ˜ ⇒ A˜(x)·B˜(x).
  - Seq˜𝒜 ⇒ ¹⁄_(1−A˜(x));
  - Set˜𝒜 ⇒ exp A˜(x);
  - Cyc˜𝒜 ⇒ log ¹⁄_(1−A˜(x)).
  Examples:
  - Connected graphs. Stirling partition numbers ¹⁄_n!(e^x − 1)ⁿ.
  - Permutations 𝒫 = Seq˜[1] = Set˜(Cyc˜[1])) ⇒ ¹⁄_(1−x) = exp( log ¹⁄_(1−x) )
  - Bell numbers B_k = #{all set partitions of [k]} ⇒ ℬ˜ = Set˜ Set˜_≥1[1] ⇒ B˜(x) = exp(e^x − 1).
- 9/24: Lagrange inversion formula for Cayley trees
  Reading: [St] Vol 2, §5.3, p 22; §5.4, p 36. [FS] §I.5, p 64; §II.5, p 125. [HHM] §1.3.4, p 43.
- 9/26: Directed Product, Euler numbers, Bivariate generating functions. Reading: [FS] §II.6.3, p 139. ⊞ Notes
  - (𝒜˜)^min∗ ℬ˜ = { (a_I, b_J) with a ∈ 𝒜˜, b ∈ ℬ˜, I ⊔ J = [k], 1 ∈ I } ⇒ ∫ ^d⁄_dx(A˜(x)) B˜(x) dx
  - Euler number E_k = #ℰ_k = #{w ∈ 𝒮_k with w(1) > w(2) < w(3) > ··· },
  - 𝒥˜ = ∐_k≥0 ℰ˜_2k+1 , 𝒥˜ = 𝒥˜∗ [1]^min∗𝒥˜ ⊔ [1]
  - J˜(x) = ∫ J˜(x) ^d⁄_dx(x) J˜(x) dx + 1 ⇒ J˜(x) = tan(x)
  - Bigraded labeled class 𝒜˜ with size |a| = k, vertex labels [k], and weight wt(a) = ℓ
  - Double counting number A_k,ℓ = #{a ∈ 𝒜 with |a| = k and wt(a) = ℓ}.
  - Bivariate generating function A˜(x,y) = ∑_k,ℓ≥0 A_k,ℓ ^x⁄_k! y^ℓ.
  - Permutations 𝒮˜ = ∐_k 𝒮_k with |w| = k and wt(w) = cyc(w) = number of cycles of w.
  - 𝒮˜ = Set˜ Cyc˜ [1] ⇒ S˜(x,y) = exp(y log ¹⁄_(1−x)) = (1 − x)^−y
  - ∑^k_ℓ=1 S_k,ℓ y^k = ∑^k_ℓ=1 [k | ℓ] y^k = ¹⁄_k! (^d⁄_dx)^k S˜(x,y)|_x=0 = y(y+1)···(y+k−1) = y^k
- 9/29-10/3: Polya theory, Burnside lemma, counting up to symmetry. Reading:
  - Math 481 Polya Notes and Polya HW.
  - [HHM] §2.7, p. 190.
  - [St] vol 2, §7.24.
  - [FS] §I.6, p. 83-86, §III.3.2, p. 166; §A.4, p. 729.
  - Kerber, Applied Finite Group Actions, unlabeled graphs in Lemma 2.3.2 p. 70.
  Notes
  - Permutation group G ⊂ 𝒮_k acting on finite class ℱ . Orbits ℱ = ^ℱ⁄_G ,
    Burnside formula: orbit counting #ℱ = ¹⁄_#G ∑_w∈G #ℱ^w for fixed sets ℱ^w = {f ∈ ℱ ∣ w(f) = f}
    For functions ℱ = {f : [k] → [n]}, #ℱ^w = n^cyc(w) where cyc(w) = # cycles of w.
    Proof: #ℱ = ^#𝒮⁄_#G where 𝒮 = {(w,g) ∈ 𝒮_k × ℱ ∣ w(f) = f}.
  - Cycle index Z_G(z₁, . . . , z_k) = ∑_w∈G z₁^cyc₁(w) ··· z_k^cyc_k(w) where cyc_i(w) = # length i cycles of w
  - Polya: Multi-graded class 𝒜 with wt₁(a), . . . , wt_n(a)
    Multi-variable gen fun A(y^→) = A(y₁, . . . , y_n) = ∑_a∈A y₁^wt₁(a) ··· y_k^wt_n(a)
    Interval 𝒩 = [n] with N(y^→) = y₁ + ··· + y_n, diagonal Δ^(k)𝒩 = {(j, . . . , j) ∈ 𝒩^k}, gen fun N^(k)(y^→) = y₁^k + ··· + y_n^k
    Functions ℱ = {f : [k] → [n]} with wt_i(f) = #f⁻¹(i)
    Polya Formula: ℱ(y^→) = ¹⁄_#G Z_G(N⁽¹⁾(y^→), N⁽²⁾(y^→), . . . , N^(k)(y^→))
  - Unlabeled class ℬ, Multisets 𝒞 = MSet_k(ℬ) ⇒ C(y) = ¹⁄_k! Z_{𝒮_k}( B(y), B(y²), . . . , B(y^k) )
    Proper sets 𝒞 = Set_k(ℬ) ⇒ C(y) = ¹⁄_k! Z_{𝒮_k}( B(y), −B(y²), B(y³), . . . , (−1)^k B(y^k) )
- 10/6-10/10: Finite field Grassmannians ⊞ Notation
  Reading: §1.10.2; §1.7, esp. Prop 1.7.2; §1.3, esp. Prop 1.3.13. Wikipedia on finite fields.
  - q-integer: [n]_q = 1 + q + q² + ··· + qⁿ⁻¹ = ^(qⁿ−1)⁄_(q−1) = #Pⁿ⁻¹(F_q)
  - q-factorial: [n]^!_q = [n]_q [n−1]_q ··· [1]_q = ∑_{w∈S_n} q^inv(w) = #Flag(F_qⁿ)
  - Gaussian q-binomial coefficient: (n | d)_q = ^{[n]^!_q} / _{[d]^!_q (n−d)^!_q} = ∑_I q^|I| = #Gr(d, F_qⁿ)
  - Three indexing sets for Schubert cells of Gr(d, Fⁿ)
    - subsets I = {i₁ < ··· < i_d} ⊂ [n] with weight wt(I) = ∑_j (i_j−j)
    - partitions λ = (λ₁ ≥ ··· ≥ λ_d ≥ 0) = (i_d−d , . . . , i₁−1) with weight wt(λ) = ∑_j λ_j
    - Grassmannian permutations w ∈ S_n^(k) ≅ S_n / S_d×S_n−d
      w = (i₁ < ··· < i_d | j₁ < ··· < j_n−d) with weight wt(w) = inv(w)
  - [St] denotes [n]_q , [n]^!_q , (n choose d)_q by boldface n , n! , (n choose d)
  - For a multiset M = {1^m₁, 2^m₂,...} with n = ∑_i m_i elements, a permutation of M means an ordering of the n elements, corresponding to a coset in the group quotient S_M = S_n / S_m₁ × S_m₂
  - Inversion diagram: I(w) = { (i, j) | i < j and w(i) > w(j) }.
  - Rothe diagram: D(w) = (1×w) Inv(w) = { (i, j) | i < w⁻¹(j) and w(i) > j }
  - Lehmer code: c(w) = (c₁,..., c_n), c_i = #{ j | i < j and w(i) > w(j) }
  - Flattening: Flat(w) = (f₁,..., f_n), f_i = #{ j | i ≤ j and w(i) ≥ w(j) } = c_i + 1
  - Inversion length: inv(w) = #I(w) = #D(w) = |c(w)|