# Counting compositions of an integer

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

-
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

## 1 Answer

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

-