2
$\begingroup$

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

  • 0
    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 ;-) – 2012-03-07
  • 0
    @dtldarek I added the condition $\sum_{i=1}^n 2^{-l_i}>1$ which i think will rule out the trivial small asymptotic growth. – 2012-03-07
  • 0
    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. – 2012-03-08

1 Answers 1

1

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