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$.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Jun 27, 2012 at 3:23
  • $\begingroup$ Actualized question, but this is too an interesting question $\endgroup$
    – Sebastian Valencia
    Jun 27, 2012 at 3:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jack Schmidt
    Jun 27, 2012 at 4:17
  • 1
    $\begingroup$ @JackSchmidt: I don't find either of those in OEIS. $\endgroup$
    – Ross Millikan
    Jun 27, 2012 at 4:31
  • 2
    $\begingroup$ @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$ $\endgroup$
    – Ross Millikan
    Jun 27, 2012 at 4:33

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.