Let D_k (n) = number of partitions of n with any number repeated at most k times. (Thus D_1(n) = D(n).) O_k (n) = number of partitions of n into numbers none of which is a multiple of k. ( Thus O_2(n) = O(n).) Then D_k (n) = O_(k+1) (n) for all n. The argument using generating functions to establish D(n) = O(n) easily generalises to establish this, but the kids (ages 11 - 17) at the Boston Math Circle recently came up with a nice fun proof of this in terms of representing numbers base k. - JT
[Original Message] From: R. William Gosper <rwg@spnet.com> To: <math-fun@mailman.xmission.com> Date: 5/18/2003 4:11:57 PM Subject: Re: [math-fun] distinct and square-free factorizations
mlb>In fact, recalling this, I'd hoped to retrieve some collective memories!
acw>> Gosper showed me an absurdly intricate _analytic_ proof of this, and
bewailed the lack of a _combinatorial_ proof;
Here are my memories. Unfortunately, the TeX sources appear to to have been abandoned at Xerox PARC. Shortly after the announcement of the factorization of 2^2^2^3+1, I sent a(n unrelated) letter to the the usual gang of maniacs (Dick Askey, George Andrews, George Gasper (I think), Rich&Hilarie, etc.) that began: "Dear Thai food lovers and Rich," answering Hilarie's challenge to find a bijection between the *complements* of the odd partitions and distinct partitions. I.e., pair the not-all-differents with the not-all-odds. A very young Peter Weyhrauch and I came up with one, and then a PARC coworker, Ted Kaehler, came up with a different one! I then found a generalization of the theorem to residue classes mod k, of which #(some evens) = #(some duplicates) was the case k=2. This led to a nonobvious generating function identity. It would be nice to locate a hardcopy of that letter. --rwg
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
========================= James Tanton mathcircle@earthlink.net P.O. Box 2344 Acton MA 01720 978 635 8036 FIND *MATH CIRCLE* ON THE WEB AT: www.themathcircle.org