Let us define a superincreasing sequence of natural numbers $b_1, b_2, \ldots,b_n$:

$$ b_{i+1} > \sum_{j=1}^i b_j $$

or, as we talk about natural numbers:

$$ b_{i+1} \geq 1+ \sum_{j=1}^i b_j. $$

What is the number of such sequences with the following property:

$$ \sum_{j=1}^n b_j \leq 2^{n+1}-1. $$

A simple lower-bound estimate is $n+1$ - this is the number of superincreasing sequences which consist of powers of 2, i.e. $n$-combinations of set $\{1,2,4,\ldots,2^n\}$.

In case this is complicated to find simple exact formula, estimates will be interesting too.

UPD 1. Program generation showed the following results for the first values of $n$: 3, 9, 35, 201, 1827, 27337, 692003, 30251721... This is OEIS A125792.

UPD 2. It seems the number I was looking for is discussed in the paper V. Bakoev, Algorithmic approach to counting of certain types $m$-ary partitions (also available here).


I find $\begin {array} {c c} n& \text{sequences}\\1&3\\2&9\\3&35\\4&201 \end {array}$

which is OEIS A125972. The counting is suggestive. For $n=3$ there are $9$ beginning $1,2$; $7$ beginning $1,3$; down to $1$ beginning wit $1,6$ for a total of $25$ beginning with $1$. Similarly there are $9$ beginning with $2$ and $1$ beginning with $3$. For $n=4$ there are $9^2$ beginning $1,2$; $7^2$ beginning $1,3$; down to $1^2$ beginning $1,6$ for $165$ beginning with $1$, and again $95^2$ beginning $2,3$ and so on. It clearly needs some induction.

  • $\begingroup$ I generated all the sequences for small $n$'s and found a bit different numbers: 3, 9, 35, 201, 1827, 27337, 692003, 30251721... And this is A125792. $\endgroup$ – Yauhen Yakimenka Nov 3 '12 at 2:27
  • $\begingroup$ Seems to be a bit of disagreement at $n=4$. Perhaps you could both check your calculations. $\endgroup$ – Gerry Myerson Nov 3 '12 at 4:55
  • $\begingroup$ @GerryMyerson: Found the error and fixed $\endgroup$ – Ross Millikan Nov 3 '12 at 6:09

In fact, the sequence is described in details of A125792. The number I was looking for is the same as the number of partitions of $2^n$ into powers of $2$, excluding the trivial partition $2^n=2^n$ (note there by Valentin Bakoev).

Perhaps the easiest practical recurrent formula is the following: $$ T(n,k) = T(n,k-1) + T(n-1,2k) $$ $$ T(n,0) = T(0,k) = 1 $$

Then the answer to the original problem is $T(n,2)$.

One can find even more discussion and references in the description of A002577 which is $T(n,2) + 1$ (in our notation).


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.