Number of ways, powers of $2$ sum up specific values

Question

Given the set $B=\{2^0,2^1, 2^2,...2^{n-1} \}$. Now you pick $n$ elements of $B$ with repetitions and sum the picked elements, e.g.

• picking every element once this sums up to $s_{1,1,...,1}=\sum_{k=0}^{n-1} 2^k= 2^{n}-1$.
• Another example would be picking $n$ times the $k$th element resulting in $s_{0,...n,...,0}=n2^k$.

I want to count the number of occurrences of all possible sums I can construct in this way, by using generating functions but I can't figure out how this works in this case.

Any help appreciated...

Answer 1

Take n=4 as an example. Look at the integer partitions of k in n parts of size at most n, with k= n to n^2. This produces all Binomial(2n-1,n-1) sets of exponents k you mentioned:
1111, 1112, 1113, 1122, 1114, 1123, 1222, 1124, 1133, 1223, 2222, 1134, 1224, 1233, 2223, 1144, 1234, 2224, 1333, 2233, 1244, 1334, 2234, 2333, 1344, 2244, 2334, 3333, 1444, 2344, 3334, 2444, 3344, 3444, 4444
Now, as an 'encoding' step, write '1233' as x1*x2*x3*x3 and sum over all;
you get Sum(all partitions p of n; m(p,n) )
with m(p,n) the monomial symmetric polynomial in n variables.
And that's just the Schur polynomial of single-part-partition {n} in n variables.
You did say '.. any help..'

Answer 2

As universalset points out in the comment above, I was already quite close with my other question. The correlation in time was not by chance. So here my result:

$$ \left(\sum_{k=0}^{n-1} x^{2^k}\right)^{n} $$ counts what I was looking for. To give an example, let $n=5$: $$ \color{green}{x^{80}}+5 x^{72}+5 x^{68}+5 x^{66}+5 x^{65}+10 x^{64}+20 x^{60}+20 x^{58}+20 x^{57}+20 x^{56}+20 x^{54}+20 x^{53}+40 x^{52}+20 x^{51}+40 x^{50}+30 x^{49}+35 x^{48}+60 x^{46}+60 x^{45}+60 x^{44}+60 x^{43}+80 x^{42}+50 x^{41}+61 x^{40}+60 x^{39}+100 x^{38}+90 x^{37}+85 x^{36}+70 x^{35}+95 x^{34}+65 x^{33}+75 x^{32}+\color{red}{120 x^{31}}+120 x^{30}+100 x^{29}+110 x^{28}+100 x^{27}+90 x^{26}+90 x^{25}+100 x^{24}+100 x^{23}+90 x^{22}+70 x^{21}+66 x^{20}+70 x^{19}+55 x^{18}+65 x^{17}+75 x^{16}+60 x^{15}+50 x^{14}+50 x^{13}+40 x^{12}+30 x^{11}+31 x^{10}+25 x^{9}+15 x^{8}+10 x^{7}+5 x^{6}+x^{5} $$ Here you see $5!$ occurrences of $31=2^5-1$ and one of $80=5\cdot 16$.