|
| |
|
|
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.
|
|
3
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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
|
|
|
EXAMPLE
|
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}.
|
|
|
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):
|
|
|
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];
|
|
|
PROG
|
(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)])
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
