FW: Re: [math-fun] distinct and square-free factorizations
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
I said
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,
12 July,1982, in fact.
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,"
No, that was a different letter. And despite this misdirection, George managed to dig up his copy and Smearox it.
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,
Treat the repeated and nonrepeated parts separately. Add together repeated parts in pairs until no repeats remain. Then, iteratively bisect the even initially unique parts until only odds remain. Reverse: Treat the odd and even parts separately. Iteratively bisect the even parts until only odds remain. Iteratively add together pairs that were intially odd. This process also serves to biject distinct partitions with odd ones.
and then a PARC coworker, Ted Kaehler, came up with a different one!
Some evens to some duplicates: If any part is repeated, do nothing(!), else iteratively bisect the evens 'til none remains. Some duplicates to some evens: If any part is even, do nothing(!), else iteratively pair duplicates until none remain.
I then found a generalization of the theorem to residue classes mod k, of which #(some evens) = #(some duplicates) was the case k=2.
I.e., # partitions with k-tuples = # with multiples of k.
This led to a nonobvious generating function identity.
Actually, it's fairly elementary, but funny-looking: 1-(1-q)(1-q^2) ... = sum (1-q)(1-q^2)...(1-q^(n-1)) q^n n>0 = sum q^n (1-q^(n+1))(1-q^(n+2))... n>0 The nonobvious identities came from generalizing a Ramanujan identity from George's Theory of Partitions book, which implies: The partitions of n with largest part odd and < twice the smallest part = " " " " " smallest part unique and >= half the largest. I'll type it up if there's any interest.
It would be nice to locate a hardcopy of that letter.
Thanks, George!
--rwg
participants (2)
-
James Tanton -
R. William Gosper