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