5
$\begingroup$

Let U be the set $U=\{(1,2,3,\ldots,2^m)\}$. Let $A$ and $B$ partitions of $U$, such that $A \cup B$ is the set $U$, and their intersection is empty, and adding the elements of the first set is the same number of the addition of the elements of the second set $B$.

How many $A$ and $B$ is there?

I mean, if $U=\{1,2,3,4\}$, there exist just a single pair of sets $A$, and $B$. $A=(3,2)$ and $B=(4,1)$, because $3+2=4+1$, i want to know how many $A$ and $B$s exists for bigger sets $U$.

  • 1
    You're asking, for how many subsets of $\{{1,2,\dots,2^m\}}$ is the sum of the elements $2^{m-1}(2^m+1)$. I'd be surprised if there were a nice answer to this.2012-06-27
  • 0
    Actualized question, but this is too an interesting question2012-06-27
  • 1
    In your previous question, you also needed A to have $2^{m-1}$ elements, in order for constant polynomials to agree. If you add this condition to this problem, the answers are 0, 2, 8, 526, ... or 0, 1, 4, 263, ... if you don't care which one is A and which is B.2012-06-27
  • 1
    @JackSchmidt: I don't find either of those in OEIS.2012-06-27
  • 2
    @GerryMyerson: Isn't the sum of the subset supposed to be $2^{m-2}(2^m+1)$. There is one division by 2 for the triangle number and one because the sum is half the sum of $U$2012-06-27
  • 0
    @Ross, yes, thanks.2012-06-27

1 Answers 1

3

If instead we take $U=\{{1,2,3,\dots,m\}}$, then the answer is easily seen to be nonzero only if $m$, reduced modulo 4, is 0 or 3. The sequence of values is tabulated at the Online Encyclopedia of Integer Sequences; it starts $$\eqalign{&0, 0, 1, 1, 0, 0, 4, 7, 0, 0, 35, 62, 0, 0, 361, 657, 0, 0, 4110, 7636, 0, 0, 49910, 93846, 0, 0,\cr &632602, 1199892, 0, 0, 8273610, 15796439, 0, 0, 110826888, 212681976, 0, 0,\cr &1512776590, 2915017360, 0, 0, 20965992017, 40536016030, 0, 0, 294245741167,\cr &570497115729\cr}$$ No formula is given.

If we restrict to powers of two, the sequence starts $$0,0,1,7,657=9\times73,15796439=41\times385279,24435006625667338=(2)(727)(182764397)(91951)$$ This sequence is not tabulated. I am not optimistic about finding any useful formula for these numbers.