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 Wolfram Alpha,
Mathematica,
or the like whenever helpful.
Please do not look up answers; but if you do get help from an outside source, give explicit credit.
Click ⊞ to open sections.
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.
8/28:Method of generating functions for binomial coefficients
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 S ⊂ [n],
Multiplicity Transform to {0,1}n gives generating function A(x) = (1+x)n, Taylor coefficient formula (n | k) = nk/k! .
Deletion Transform & Pascal Triangle. Quotient Principle gives formula directly.
HW: Do ((n | k)) = n-multichoose-k similarly.
8/30:Method of generating functions for Fibonacci numbers.
Reading: Math 481 Toolkit: Method of Generating Functions,
Notes 10/4: Fibonacci numbers.
Gen fun F(x) = x⁄(1−x−x2), partial fraction expansion, Binet Formula, asymptotic. To find combinatorial class: substitute z = x+x2, expand to count hopscotch boards. HW: Solve a similar recurrence.
9/1 & 9/6:Twelvefold Way:
Reading: [St] §1.9. Math 482 HW 1/8 & 1/10.
Principle of Inclusion-Exclusion:
[St] §2.1.
Math 481 HW 1/25−1/29,
Notes 1/27.
Functions, balls & baskets, dist & indist, familiar numbers, surj(k,n) & set partitions,
((n | k−n)) = (k−1 | n−1).
{n | k} via ordinary gen fun {n | k} = k{n−1|k} + {n−1|k−1}, partial fractions. PIE via characteristic funs, surj(n,k). HW: Deletion recurrences, derangements via PIE.
9/8:Generating Function Diagram.
Reading: [FS] Ch I.1, I.2.
Fill out Twelvefold Way, applying counting Principles for finite sets: Sum, Product, Difference (PIE), and Quotient (free group action).
Quotient Principle for free group actions. HW: ((n | k)) ≠ nk⁄k!
9/11:
Number partitions, transforms.
Reading: [St] §1.8. [FS] Ch I.3.
Wikipedia on partitions.
λ = (λ1 ≥ ··· ≥ λn) ↔ 1m1
2m2 3m3···,
Young diagram, transpose λ'
Generating function P(x) = ∏i≥0 (1−xi).
Complement: Hardy-Ramanujan p(k) ∼ 1⁄4n√3 exp(π√(2n)⁄√3).
HW: False deletion recurrence, partition identities from gen funs
9/13 & 15:
Involution Principle:
[St] §2.6, up to Eq (2.31).
[Stanton-White], Ch 4, p. 110.
Euler Pentagonal Number Theorem, Franklin's involution.
Reading:
Wikipedia.
Complements: Vershik asymptotic, modular function η(q).
HW: PIE from Involution Principle;
(1+x)n · 1⁄(1+x)n = 1.
Derangements via PIE.
10/9−13: Cayley trees, Lagrange inversion.
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.
Math 481 Graph Notes II,
HW 3/25.
10/16: Unlabeled operations: Set and MSet.
Unlabeled trees & Dlog method for recurrences.
Reading: Unlabeled operations: [FS] §I.2, p 24,
[W] §3.14−17, p 92.
Dlog method: [W] §1.6, pp 22−23.
10/23: Polya theory,
Burnside lemma,
counting up to symmetry.
Reading:
Incidence algebra for poset P = D∞ , positive integers ordered
by divisibility d | n
Equivalence of intervals [a,b] ∼ [c,d]
⇔
b⁄a = d⁄c,
stronger equivalence than poset isomorphism [a,b] ≅ [c,d].
Reduced incidence algebra
R(P) = {f ∈ I(P)
with f[a,b] = f[c,d] for [a,b] ∼ [c,d]}
=
⨁n≥1C n,
where n
= ∑i≥1 [i, in] multiplies as
n·m
= nm
R(P) ≅ ⨁n≥1C n−s,
with
∑n≥1 ann
≅
∑n≥1
ann−s = F(s)
Dirichlet series F(s) usually converges for s ∈ C
with Im(s) > 1 or Im(s) > C for some C.
Riemann zeta function ζ(s) =
∑n≥1 n−s
Euler product: D∞
≅ N × N × ···
given by n = 2i1 3i2 5i3 7i4
11i5 ···
for ij ∈ N chain poset:
ζ(s)
=
∑n≥11⁄ns
=
∏p1⁄(1−p−s) ,
where p runs over all primes.
Here each factor
1⁄(1−p−s)
is the zeta function 1⁄(1−x)
of the corresponding chain poset N,
with the substitution x = p−s.
Grassmannian permutations
w ∈ Sn(k)
≅ Sn / Sd×Sn−d
w = (i1 < ··· < id | j1 < ··· < jn−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 = {1m1, 2m2,...} with
n = ∑i mi elements, a
permutation of M
means an ordering of the n elements,
corresponding to a coset
in the group quotient SM = Sn / Sm1 × Sm2