- The Prob Method: Isn't that just counting?
- Kolg complexity: Isn't that just the Prob Method?
- Information complexity: Isn't that just Kolg complexity?
- Counting: Isn't that just Information Complexity?
(Schur's Theorem) Let a1,a2,...,aL be denominations of coins such that no number ≥ 2 divides all of them. Then, for large n, the number of ways to make change of n cents isFor full proof see here. My writeup is based on that in Wilf's book generatingfunctionology (the title page really does use a small g for the first letter).nL-1/((L-1)! a1 a2 ... aL) + O(nL-2)
The above was my INTENDED POST. However, when I showed the Gen-function proof of Schur's theorem to some students, one of them, Sam (a HS student), came back the next day with a purely combinatorial proof. It was not completely rigorous but I am sure that he and most of my readers, could make it so without too much effort. While having two proofs (Gen-function and Combinatorial) is MORE enlightening for me and for my readers, it does dampen my point that this is a theorem for which the gen-function proof is easier. I COULD argue that the gen-function proof did not require as much cleverness, or that once you put in the rigor it is harder, but I don't really have confidence in those arguments. I include the combinatorial proof in the writeup pointed to above. Which proof is better? A matter of taste. However, I hope you enjoy both of them!