Date: Wed, 18 Mar 1998 21:05:00 -0600 (CST)
From: Dave Rusin <rusin>
To: xxb1@psu.edu
Subject: Re:  More Number Theory

>Suppose you have a set,
>
>{1,2,3,4...,r}
>
>How many ways are there to partition the set into two sets such that the sum of
>the two sets are equal ?

I don't know. The sum of 1+...+r  is r(r+1)/2, which isn't even unless
r=0 or -1 mod 4. But in those cases, the two parts of the divisions give
all the partitions of  x = r(r+1)/4  whose terms are all distinct and
at most equal to  r; the number you asked about is half that number of
restricted partitions.

You can more generally ask about the number  T(x,r)  of partitions of _any_
integer  x  all of whose summands are distinct and bounded by  r.
This is one of the sets of numbers in Sloane's table of integer
sequences (it's sequence  A026820 ). I don't expect there's any nice
formula for this as a function of  x  and  r.  I suppose it's possible
that your subsequence  T( r(r+1)/4, r )/2  admits a nice description, but
I don't see any. Here are the first few terms:

r=-1 mod 4:  1, 4, 35, 361, 4110, ...
r= 0 mod 4:  1, 7, 62, 657, 7636, ...

There may be a simple way to compute the number of these partitions
inductively; I just listed them all and counted. The maple script I
used is below.

Some information about partitions may be found on
	index/05-XX.html

dave


s():=proc()
local a,b,i,j,x,y,le;
global sq,lst;
    le := nops(sq);
    x := [seq(sq[i],i = 1 .. le(sq)-2)];
    if 2 < sq[le]-sq[le-1] then
        x := [op(x),sq[le-1]+1];
        a := sq[le]-1;
        b := sq[le-1]+2;
        while 2*b < a do  x := [op(x),b]; a := a-b; b := b+1 od;
        x := [op(x),a]
    else x := [op(x),sq[le-1]+sq[le]]
    fi;
    sq := x:
end:

mom:=proc(N)
local i;
global sq;
    sq := [0,1/4*N*(N+1)];
    s();
    i := 0;
    while sq[1] = 1 do
        if sq[nops(sq)] <= N then i := i+1; print(i,sq) fi; s()
    od:
    RETURN(i):
end:

for i from 1 to 4 do mom(4*i); od:

#You can delete the "print" statement, and speed up execution time.
#This is hardly optimized code!

==============================================================================

Date: Thu, 19 Mar 1998 09:09:00 -0600 (CST)
From: Dave Rusin <rusin>
To: xxb1@psu.edu
Subject: Re:  More Number Theory

I thought about your question a little more and realized it _is_ a
"known" sequence. In fact, if you phrase the question right, you can 
even get non-zero values when  r  is congruent to  1 or 2 mod 4: the
numbers you want are half these:

%I A025591 
%S A025591 1,1,1,2,2,3,5,8,14,23,40,70,124,221,397,722,1314,2410,4441,8220,1527
2, 
%T A025591 28460,53222,99820,187692,353743,668273,1265204,2399784,4559828,86792
80,
%U A025591 16547220,31592878,60400688,115633260,221653776,425363952,817175698
%N A025591 Maximum coefficient of PROD k<=n, x^k+1.
%R A025591
%O A025591 0,4
%K A025591 nonn
%A A025591 wilson@ctron.com

This information is in Sloane's integer sequence database:
	http://www.research.att.com/~njas/sequences/


dave