A390488 Number of partitions of n into distinct parts where each part is at most the sum of the previous two.

1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 8, 8, 9, 10, 13, 14, 17, 18, 21, 22, 26, 28, 35, 38, 44, 48, 56, 59, 70, 75, 86, 96, 111, 120, 141, 155, 177, 196, 222, 243, 277, 305, 342, 381, 430, 473, 535, 595, 665, 740, 828, 916, 1026, 1137, 1265, 1402, 1562, 1726, 1920, 2123

Offset

0,4

Comments

All partitions with at most two parts automatically satisfy the condition; the restriction applies only from the third part onward. Sequence is nondecreasing.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..500

Formula

a(n) = number of distinct partitions lambda of n such that lambda_i <= lambda_{i-1} + lambda_{i-2} for all i >= 3.

Example

For n = 6, the distinct partitions are (6), (1,5), (2,4), (1,2,3). All satisfy lambda_3 <= lambda_2 + lambda_1, so a(6) = 4.
For n = 7, the distinct partitions are (7), (1,6), (2,5), (3,4), (1,2,4); the last partition is disallowed because 4 > 2 + 1. Thus a(7) = 4.

Maple

b:= proc(n, x, y, i) option remember; `if`(n=0, 1,
     `if`(i>n or i>x+y, 0, b(n-i, y, i, i+1)+b(n, x, y, i+1)))
    end:
a:= n->  b(n$3, 1):
seq(a(n), n=0..80);  # Alois P. Heinz, Jan 04 2026

Mathematica

goodQ[p_] := And @@ Table[p[[i]] <= p[[i-1]] + p[[i-2]], {i, 3, Length[p]}];
a[n_] := Length @ Select[IntegerPartitions[n, All, All, True], goodQ];
Table[a[n], {n, 0, 50}]

Prog

(Python)
def partitions_distinct(n, max_part):
    if n == 0:
        yield ()
        return
    if max_part == 0 or n < 0:
        return
    if max_part <= n:
        for p in partitions_distinct(n-max_part, max_part-1):
            yield p + (max_part, )
    yield from partitions_distinct(n, max_part-1)
def good(p):
    return all(p[i] <= p[i-1] + p[i-2] for i in range(2, len(p)))
def a(n):
    if n == 0:
        return 1
    return sum(1 for p in partitions_distinct(n, n) if good(p))
print([a(n) for n in range(0, 51)])

Crossrefs

Cf. A000009, A000045, A000837.

Sequence in context: A296371 A337601 A340283 * A324744 A097920 A029042

Adjacent sequences: A390485 A390486 A390487 * A390489 A390490 A390491

Keyword

nonn

Author

James Morgan, Dec 05 2025

Status

approved