| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1294.1 | | GUESS::DERAMO | Dan D'Eramo | Tue Sep 11 1990 23:00 | 4 |
| I think the proof I read draws columns / rows of dots and
counts them in two ways.
Dan
|
| 1294.2 | binary arithmetic | ALLVAX::JROTH | It's a bush recording... | Wed Sep 12 1990 07:03 | 21 |
| Consider some examples (where 5.1 means 5 1's: 1+1+1+1+1):
odd parts unequal parts
--------- -------------
2.1 + 1.5 2 + 5
4.1 + 1.3 4 + 3
1.1 + 2.3 1 + 6
7.1 4 + 2 + 1
1.7 7
1.1 + 1.7 1 + 7
3.1 + 1.5 3 + 5
2.1 + 2.3 2 + 6
5.1 + 1.3 4 + 1 + 3
8.1 8
You can always break the repeat count for each odd number into a
binary expansion and multiply each power of 2 by that odd number to
make corresponding unequal numbers that add up the same.
- Jim
|
| 1294.3 | early morning mental callisthenics for Jim | HERON::BUCHANAN | combinatorial bomb squad | Wed Sep 12 1990 07:30 | 43 |
| > You can always break the repeat count for each odd number into a
> binary expansion and multiply each power of 2 by that odd number to
> make corresponding unequal numbers that add up the same.
Yes.
> odd parts unequal parts
> --------- -------------
> 1.1 + 1.7 1 + 7
> 3.1 + 1.5 3 + 5
> 2.1 + 2.3 2 + 6
> 5.1 + 1.3 4 + 1 + 3
> 8.1 8
Nearly (but I don't know how you can think at all at 6.03 am)
3.1 + 1.5 2 + 1 + 5
1.3 + 1.5 3 + 5
Another one is:
Show that the number of odd, unequal partitions is equal to the
number of symmetric partitions.
(Definition of symmetric partition: you can draw a partition like this:
*
**
*****
You can then flip it in the major axis to get:
*
*
*
**
***
A symmetric partition is one which is the same as its flipside, eg:
*
*
**
**** )
|
| 1294.4 | | HERON::BUCHANAN | combinatorial bomb squad | Fri Sep 14 1990 04:58 | 18 |
| > Show that the number of odd, unequal partitions is equal to the
>number of symmetric partitions.
C'mon chaps, this is *easy*. To make it completely clear, the
odd, unequal partitions for some small n are:
n = 1: 1
n = 2: -
n = 3: 3
n = 4: 1,3
n = 5: 5
n = 6: 1,5
n = 7: 7
n = 8: 1,7
n = 9: 9 or 1,3,5
...
Andrew.
|
| 1294.5 | Proof by staring | NOEDGE::HERMAN | Franklin B. Herman DTN 291-0170 PDM1-1/J9 | Fri Sep 14 1990 23:14 | 64 |
|
Re: -1:
>> Show that the number of odd, unequal partitions is equal to the
>> number of symmetric partitions.
OK Andrew, I finally got it by staring at the "Ferrar graphs" of the
symmetric partitions:
Each odd number determines a symmetric right angle bracket,
hence a symmetric partition of that odd number, e.g.:
1 ---> * 1
3 ---> * 1 + 2
* *
5 ---> * 1 + 1 + 3
*
* * *
7 ---> * 1 + 1 + 1 + 4
*
*
* * * *
Now just nest the angle brackets corresponding to each
odd distinct part in order of size, e.g.
1 + 7 ---> * 1 + 1 + 2 + 4
*
* *
* * * *
1 + 3 + 7 ---> * 1 + 3 + 3 + 4
* * *
* * *
* * * *
--------------------------------------------------------------------------------
Here's another one to try and find an explicit correspondence:
Show that number of partitions of n such that each positive integer,
k say, can only occur atmost k-1 times is the same as the number
of partitions of n into non-squares.
--------------------------------------------------------------------------------
Finally,
Is there some general result to the effect that if one can prove
that the number of two types of different partitions are the
same using generating functions then some "canonical" correspondance
between the two types can also be found.
-Franklin
|
| 1294.6 | square smashing | HERON::BUCHANAN | combinatorial bomb squad | Tue Sep 18 1990 06:57 | 30 |
| > Show that number of partitions of n such that each positive integer,
> k say, can only occur atmost k-1 times is the same as the number
> of partitions of n into non-squares.
Using generating functions its trivial, but we want an explicit
construction.
Let A = a_1, a_2, ... a_t define a partition of n, where a_i is the
number of parts of size i. Define a smashing map, S, from one partition, A,
to another, B, by b_i = a_i + i*a_(i�) (i not a square)
= i*(a_i�) (i a square)
Iterate S until a fixpoint is reached (ie, all the squares are
smashed.) So C = S(C) = T(A). If A is such that a_i < i for all i, then
T is invertible, whence the result immediately.
> Is there some general result to the effect that if one can prove
> that the number of two types of different partitions are the
> same using generating functions then some "canonical" correspondance
> between the two types can also be found?
Doesn't Andrews' book (.0) discuss a general theory of identities
for partitions? Is that relevant to your discussion here, and if so what
are his conclusions?
My intuition says that the answer is "No" to your question, btw.
Shoot me down in flames!
Regards,
Andrew.
|
| 1294.7 | Stanton's "cranks" | NOEDGE::HERMAN | Franklin B. Herman DTN 291-0170 PDM1-1/J9 | Thu Sep 27 1990 23:39 | 176 |
|
As far as the Andrew's book, the question of whether pure
combinitorial proofs can always be found to replace pure generating
function proofs never arises directly. He does however define a notion of
partition "ideal" with an associated "order" to deal with arbitrary
partition identities; however it is incomplete theory and is devoid
of pure combinitorial arguments.
On a few occasions he will pose as an open question if a various
result just proved in a non-combinitorial way can done combinitorially.
A few times he provides a combinitorial proof of a result previously
proven with other means if it is simpler and provides more insight.
The best example of this in the book are the two proofs of a result
of Euler about generating functions which is used to prove other
partition identities namely:
oo oo
____ n� _______
\ q | | -1
1 + > ------------------------ = | | (1 - q^n) (*)
/ (1-q)�(1-q�)�...(1-q^n)� | |
---- n=1
n=1
This is first proved by specializing a unmotivated hypergeometric
function identity whose proof is strictly computational on the
conceptual level of verifying a high school trig identity where
the technique is to reduce each side to a common expression; hardly
enlightening.
The second proof, the combinatorial one due to Durfee, I could'nt
resist in repeating it here at the end of this note for its
beauty and simplicity.
Getting back to the issue of finding combinitorial proofs for all
partition results, I'm now more inclined to believe so after asking
around for last couple of weeks and being directed to some
references on the work of D. Stanton who has recently generalized
F. Dyson's notion of the rank of a partition (= largest part minus
number of parts) to family of "cranks". Supposedly, he has
successfully used these cranks together with the help of symbolic
computation to provide pure combinitorial proofs of the spectacular
Ramanujan conjectured congruences:
a b c
If d = 5 * 7 * 11 and 24 * m = 1 (mod d) then
a [_ (b+2)/2 _] c
p[m] = 0 (mod 5 * 7 * 11 )
where [_ _] denotes is the greatest integer function.
Apparantly F. Dyson had conjected that the special two cases:
p[5n + 4] = 0 (mod 5) and p[7n + 5] = 0 (mod 7)
would drop out if one could show that his rank mod 5 (resp, mod 7)
divides the partitions of 5n + 4 (resp, 7n + 5) into equinumerous
sets. This was subsequently proven by A. Atkin using properities
of modular forms which themselves require non-trivial complex analytic
techniques. (BTW these are the same types of ubiquitious modular
forms (also know as automorphic forms, some of which are Eisenstein series)
discussed in the very legitimate annoucement pulled off the net in
note 975 of this conference on the finiteness of Tate-Shafarevich
Group). Andrews further goes on to state in his book (published in 1976)
that all known proofs of any of these congruences depend heavily
on the modular forms techniques.
As soon as I get the Stanton references, I'll post more.
-Franklin
As for the promised proof of (*):
The RHS of (*) is just the product formula for generating
function of the partition function, i.e., if
1 for n = 0
p[n] = or
(number of partitions of n) for n >= 1
then
oo oo oo
_______ ____ ____
| | \ kn \ n
RHS of (*) = | | ( > q ) = > p[n] q
| | / /
n=1 ---- ----
k=0 n=0
In order to motivate the next definition, first consider
the "Ferrar Graph" of the following partition of 40:
11 + 8 + 8 + 6 + 3 + 2 + 1 + 1
* * * * * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * *
* * *
* *
*
*
The "Durfee square" of a partition is the largest square of dots in its
"Ferrar" Graph. For the partition above the "Durfee square" is the 4 by 4
square outlined below:
--------
| * * * * | * * * * * * *
| * * * * | * * * *
| * * * * | * * * *
| * * * * | * *
--------
* * *
* *
*
*
The piece of graph below the square is itself the "Ferrar graph" of
the partition:
3 + 2 + 1 + 1
* * *
* *
*
*
The partition to the right of the square when reflected is the
"Ferrar graph" of the partition:
4 + 4 + 3 + 3 + 1 + 1 + 1
* * * *
* * * *
* * *
* * *
*
*
*
Thus the original partition has been transformed into perfect
square of side 4 and two other partitions whose parts are
no larger than 4.
From these considerations, its not hard to see that a given
partition can be transformed into a partition with a square
part s� where s is the side of its Durfee square and two
other partitions each of whose parts are no larger than s and
that such a decomposition is unique.
By a similiar argument for product formula for the generating
function of p[n], the generating function for the number of
partitions whose parts are no larger than s is the finite product:
1
---------------------------
(1-q)(1-q�)(1-q�)...(1-q^s)
It follows that the generating function for the number of partitions
with "Durfee square" of side s is:
q^(s�)
-----------------------------
[(1-q)(1-q�)(1-q�)...(1-q^s)]�
Summing over s>=1 yields the LHS of (*), hence the result. QED
|