A339479 Number of partitions consisting of n parts, each of which is a power of 2, where one part is 1 and no part is more than twice the sum of all smaller parts.

1, 2, 5, 13, 35, 95, 259, 708, 1938, 5308, 14543, 39852, 109216, 299326, 820378, 2248484, 6162671, 16890790, 46294769, 126886206, 347774063, 953191416, 2612541157, 7160547089, 19625887013, 53791344195, 147433273080, 404090482159, 1107545909953, 3035602173663

Offset: 1

Author

Victor S. Miller, Apr 24 2021

Keywords

• nonn

Comments

a(n) is the number of n-tuples of nondecreasing integers, which are the exponents of 2 in the partition, the first of which is 0 and which are "reduced". The 1-tuple (0) is reduced. If the tuple is (x(1), ..., x(n)), then it is reduced if (x(1), ..., x(n-1)) is reduced and x(n) <= ceiling(log_2(1 + Sum_{i=1..n-1} 2^x(i))). This sequence arose in analyzing the types of partitions of a positive integer into parts which are powers of 2.

Examples

			The a(2) = 2 partitions are {1,1} and {1,2}.
The a(3) = 5 partitions are {1,1,1}, {1,1,2}, {1,1,4}, {1,2,2}, {1,2,4}.
The a(4) = 13 partitions are {1,1,1,1}, {1,1,1,2}, {1,1,1,4}, {1,1,2,2}, {1,1,2,4}, {1,1,2,8}, {1,1,4,4}, {1,1,4,8}, {1,2,2,2}, {1,2,2,4}, {1,2,2,8}, {1,2,4,4}, {1,2,4,8}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..2285

Crossrefs

Cf. A002572, A018819, A086449, A174980, A343801.

Programs

Maple

b:= proc(n, t) option remember; `if`(n=0, 1,
     `if`(t=0, 0, b(n, iquo(t, 2))+b(n-1, t+2)))
    end:
a:= n-> b(n, 1):
seq(a(n), n=1..30);  # Alois P. Heinz, Apr 27 2021

Mathematica

b[n_, t_] := b[n, t] = If[n == 0, 1, If[t == 0, 0, b[n, Quotient[t, 2]] + b[n - 1, t + 2]]];
a[n_] := b[n, 1];
Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jul 07 2021, after Alois P. Heinz *)

PARI

seq(n)={my(v=vector(n), a=vector(n)); a[1]=v[1]=1; for(n=2, n, for(j=1, n-1, v[n-(n-j)\2] += v[j]); a[n]=vecsum(v)); a} \\ Andrew Howroyd, Apr 25 2021

Python

from functools import cache
@cache
def r339479(n, k):
    if n == 0:
        return 1
    elif k == 0:
        return r339479(n - 1, 1)
    else:
        return r339479(n - 1, k + 1) + r339479(n, k // 2)
def a339479(n): return r339479(n,0)
print([a339479(n) for n in range(1, 100)])

Formula

G.f.: x/(1 - x - B(x)) where B(x) is the g.f. of A002572.

a(n) = F(n,0) where F(0,k) = 1, F(n,0) = F(n-1,1) for n > 0 and F(n,k) = F(n-1,k+1) + F(n, floor(k/2)) for n,k > 0. In this recursion, F(n,k) gives the number of partitions with n parts where the sum of all parts smaller than the current part size being considered is between k and k+1 multiples of the part size. This function is independent of the current part size. In the case that k is zero, the only choice is to add a part of the current part size, otherwise parts of double the size are also a possibility. - Andrew Howroyd, Apr 24 2021

Extensions

Terms a(19) and beyond from Andrew Howroyd, Apr 24 2021