Today (11/03/2017) the topic is tricks of exact counting, or exact
probability, exploiting things like hidden symmetry and counting
formulas.
(This is in contrast to techniques that generally imply inequalities,
such as the pigeon-hole principle or Markov's inequality. I am also
avoiding advanced algebraic techniques, like "generating functions".)
I prepared FOUR things! (Too much, so look at them later.)
As usual, today's materials are online:
http://mathcs.emory.edu/~mic/math/1103/
1. First I'll mention a graduate textbook, Richard Stanley's
"Enumerative Combinatorics" (vol.1), that is full of great material.
The handout "Richard Stanley's Twelvefold Way" (TwelveFoldWay.pdf)
summarizes a section of that book. I brought a copy (and a few others
books on combinatorics) that I am willing to lend out.
2. Here are two "easy" problems, from old Putnams. These are easy IF
you know the formulas for gcd(x,y), lcm(x,y), and #divisors(x), in
terms of the prime factorizations of x and y.
[1980 A2]
Let r and s be positive integers. Derive a formula (a function of r and s)
for the number of ordered quadruples (a,b,c,d) of positive integers such that:
3^r 7^s = lcm(a,b,c) = lcm(a,b,d) = lcs(a,c,d) = lcm(b,c,d)
[1983 A1]
How many positive integers n are there such that n is an exact divisor
of at least one of the numbers 10^40, 20^30 ?
Can you solve them? I'm willing to tell you the basic formulas.
3. Handout "Problems on 'Hidden' Independence and Uniformity" (indep.pdf)
This is a list of exact problems exploiting "independence", a vague
notion. That is, you are somehow searching over a large space, but
with the right perspective, it turns out that part of the space does
not really matter (or is easily handled). Like I said, vague. I
don't have answers to some of these, but it is a nice set, and the
first few are fairly easy.
4. Handout 'Combinatorial Problems' (comb-prac-2015.pdf). This is a
three page handout I prepared in 2015, I will only print out the first two pages.
The first page lists five combinatorial problems. The second page has a short
hint for each problem. The third page has full solutions (look online for those).