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

  • $\begingroup$ One other question: do you want the number of different sums that are possible, or do you also want the number of different ways in which each of those sums can be obtained? $\endgroup$ – Brian M. Scott Dec 12 '13 at 0:40
  • $\begingroup$ @BrianM.Scott the latter... $\endgroup$ – draks ... Dec 12 '13 at 0:42
  • $\begingroup$ Do you expect this to have a nice answer? I can write down a generating function (as I'm sure you're aware as it's exactly the polynomial in your other most recent question), but it doesn't seem to have a simple form that facilitates computing the numbers you want. $\endgroup$ – universalset Dec 12 '13 at 1:40
  • $\begingroup$ @universalset thanks for pointing out that I was on the right way. I posted an answer and would be glad if you could have a look... $\endgroup$ – draks ... Dec 12 '13 at 23:21
  • $\begingroup$ @BrianM.Scott your first (now deleted) comment should have pointed my to the right direction. I posted an answer and would be glad if you could have a look... $\endgroup$ – draks ... Dec 12 '13 at 23:21

There is a nice computation here that uses the Polya Enumeration Theorem to treat the case when order is not important, i.e. when each multiset of choices only contributes once. Applying PET we get the species equation $$\mathfrak{M}\left(\sum_{q=0}^{n-1} \mathcal{U}^{2^q}\right).$$

This immediately gives the ordinary generating function $$F(u) = Z(S_n)\left(\sum_{q=0}^{n-1} u^{2^q}\right)$$ where $Z(S_n)$ is the cycle index of the symmetric group and the second pair of parenthesis denote cycle index substitution.

Digress for a moment to consider the labelled species $\mathcal{Q}$ given by the specification $$\mathcal{Q} = \mathfrak{P}(\mathcal{A}_1 \mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{A}_2 \mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{A}_3 \mathfrak{C}_{=3}(\mathcal{Z}) + \cdots).$$ This corresponds to the generating function $$Q(z) = \exp\left(a_1 z + a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} + \cdots\right).$$

We then have by inspection the result that $Q(z)$ is the OGF of the cycle index of the symmetric group: $$Z(S_n) = [z^n] Q(z).$$

Returning to $F(u)$ we get $$F(u) = [z^n] \exp \left(\sum_{k\ge 1} \frac{z^k}{k} \sum_{q=0}^{n-1} u^{k2^q} \right).$$

We will not pick up any large cycles of length $m$ greater than $n$ from the species since the term $z^m/m$ will prevent these from appearing in $[z^n] Q(z).$

Now to conclude note that we are only interested in $F(1)$ which gives the total number of different sums that appear and disregards their value. Observe that $$\left.\sum_{q=0}^{n-1} u^{k2^q}\right|_{u=1} = n$$ so that $$F(1) = [z^n] \exp\left(n \sum_{k\ge 1} \frac{z^k}{k}\right) = [z^n] \exp\left(n \log\frac{1}{1-z}\right) = [z^n] \left(\frac{1}{1-z}\right)^n \\= {n+n-1\choose n-1} = {2n-1\choose n}.$$

We see that the removal of the dependence on the actual value of the sum has converted the problem into an application of stars-and-bars where the value $p$ at position $k$ indicates that $p$ copies of element at position $k$ in the source vector were chosen.

Of course we have the generating functions. E.g. for $n=3$ we get $${u}^{12}+{u}^{10}+{u}^{9}+{u}^{8}+{u}^{7}+2\,{u}^{6}+{u}^{5}+{ z}^{4}+{u}^{3}$$ and for $n=5$ we have $${u}^{80}+{u}^{72}+{u}^{68}+{u}^{66}+{u}^{65}+{u}^{64}+{u}^{60} +{u}^{58}+{u}^{57}+2\,{u}^{56}+{u}^{54}+{u}^{53}\\+2\,{u}^{52}+{ z}^{51}+2\,{u}^{50}+{u}^{49}+2\,{u}^{48}+{u}^{46}+{u}^{45}+3\, {u}^{44}+{u}^{43}+3\,{u}^{42}+2\,{u}^{41}\\+3\,{u}^{40}+{u}^{39} +3\,{u}^{38}+2\,{u}^{37}+4\,{u}^{36}+2\,{u}^{35}+3\,{u}^{34}+2 \,{u}^{33}+3\,{u}^{32}+{u}^{31}+4\,{u}^{30}\\+3\,{u}^{29}+4\,{u} ^{28}+3\,{u}^{27}+4\,{u}^{26}+2\,{u}^{25}+4\,{u}^{24}+3\,{u}^{ 23}+4\,{u}^{22}+3\,{u}^{21}+4\,{u}^{20}\\+2\,{u}^{19}+3\,{u}^{18 }+2\,{u}^{17}+3\,{u}^{16}+3\,{u}^{15}+3\,{u}^{14}+2\,{u}^{13}+ 3\,{u}^{12}+2\,{u}^{11}+2\,{u}^{10}\\+2\,{u}^{9}+2\,{u}^{8}+{u}^ {7}+{u}^{6}+{u}^{5}.$$ The reader may want to verify some of these. E.g. the three multisets for the sum $15$ are $1+1+1+4+8, 1+2+2+2+8$ and $1+2+4+4+4.$

  • $\begingroup$ Could you explain the fractured symbols? $\endgroup$ – draks ... Jul 3 '14 at 11:58
  • $\begingroup$ Wikipedia has this article. The operator $\mathfrak{M}$ represents unlabelled multisets, $\mathfrak{P}$ represents labelled / unlabelled sets and $\mathfrak{C}$ represents oriented labelled / unlabelled cycles. $\endgroup$ – Marko Riedel Jul 3 '14 at 22:21

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

  • $\begingroup$ Somehow I miss for example $1121$ in your set... $\endgroup$ – draks ... Dec 12 '13 at 23:24
  • $\begingroup$ @draks: I took it that 1121 and 1112 are equivalent since you pick them from an (orderless) set B. Picking 'm with repetitions should not imply that order matters, so why not order them? $\endgroup$ – Wouter M. Dec 13 '13 at 8:26
  • $\begingroup$ Gotta think about that, thx for your time... $\endgroup$ – draks ... Dec 13 '13 at 9:52

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


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.