Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. – Gerry Myerson Jun 27 '12 at 3:23
Actualized question, but this is too an interesting question – Sebastian Griotberg Jun 27 '12 at 3:36
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. – Jack Schmidt Jun 27 '12 at 4:17
@JackSchmidt: I don't find either of those in OEIS. – Ross Millikan Jun 27 '12 at 4:31
@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$ – Ross Millikan Jun 27 '12 at 4:33
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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