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 $k>0$ and $(l_1,\ldots,l_n)$ be given with $l_i>0$ and $\sum_{i=1}^n 2^{-l_i} > 1$(and the $l_i$′s need not be distinct). How do I count the number of ordered sums that add up to $k$ that involve the $l_i$'s.

For example if $k=4$ and $l_1=2, l_2=2, l_3=4$, then $$k = l_1+l_1$$ $$k = l_1+l_2$$ $$k = l_2+l_1$$ $$k = l_2+l_2$$ $$k = l_3$$ And so there are $5$ ways. This is not really a composition of the integer since $l_1$ and $l_2$ are both $2$ but considered distinct.

If there is not a reasonably simple expression, is there some known asymptotic behavior as a function of $k$ with $(l_1,\ldots,l_n)$ fixed? In particular I would like to know if the condition $\sum_{i=1}^n 2^{-l_i} > 1$ guarantees that the growth will be like $a^k$ where $a>2$.

share|cite|improve this question
You need specify something more. Without that you can get examples like $(l_i = 2^{i-1})$ that have always exactly one combination that sums up to $k$, on the other hand you can get $(l_1 = 1, l_2 = 1)$ and you get always exactly $2^k$ ways of representing $k$. This range, from $1$ to $2^k$ is pretty big. From what I can see if $l_i$ are integers, then you can't get worse than $n^k$, but if $l_i$ could be $l_i = 2^{-i}$ then there may be even more possibilities. Have fun ;-) – dtldarek Mar 7 '12 at 23:26
@dtldarek I added the condition $\sum_{i=1}^n 2^{-l_i}>1$ which i think will rule out the trivial small asymptotic growth. – user782220 Mar 7 '12 at 23:43
Sorry, I was wrong. Even without that condition you will get exponential growth (if $n > 1$, for $n = 1$ there's no much there). For example with $(l_1 = 1, l_2 = 2)$ you will get at least $2^{(k/2)}$ different representations: just treat $l_1 + l_1$ and $l_2$ like new $l_1'$ and $l_2'$ -- then you have to get $k/2$ and that you can do in $2^{(k/2)}$ ways. However, from my intuition both the base and the exponent may vary. – dtldarek Mar 8 '12 at 0:29
up vote 0 down vote accepted

I realized that what I am asking for can be phrased as a recurrence relation and thus should be answerable with standard techniques for recurrence relations.

$$N(k)=n_1 N(k-1)+ n_2N(k-2) + \cdots+ n_m N(k-m)$$

where $n_i$ is the number of $l$'s equal to $i$.

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.