A348850 a(n) is the number of labeled rooted unordered binary trees T where the nodes are labeled with distinct positive integers, the root has label n, each parent label equals the sum of its children labels, and T cannot be extended.

1, 1, 1, 1, 2, 2, 3, 5, 9, 10, 14, 22, 33, 57, 66, 94, 132, 188, 317, 454, 576, 806, 1083, 1535, 2342, 3215, 5231, 5656, 8545, 10804, 15226, 21153, 30342, 44536, 63165, 73877, 107241, 133994, 178497, 247564, 331695, 472331

Offset

1,5

Comments

For any n > 0:

- we can imagine a variant of Grundy's game where we start with n at root position,

- and each move consists in adding to a leaf, say w, two children, u and v such that 0 < u < v and u+v = w and u and v do not already appear in the tree,

- a(n) gives the number of final positions (where no move is possible).

Links

Table of n, a(n) for n=1..42.

Rémy Sigrist, PARI program for A348850

Wikipedia, Grundy's game

Example

For n = 1, 2, 3, 4: a(n) = 1:
          |         |         |         |
          1         2         3         4
                             / \       / \
                            1   2     1   3
For n = 5, 6: a(n) = 2:
          |         |         |         |
          5         5         6         6
         / \       / \       / \       / \
        1   4     2   3     1   5     2   4
                               / \       / \
                              2   3     1   3

Prog

(PARI) See Links section.

Crossrefs

Cf. A124973, A346523, A348851.

Sequence in context: A039822 A025591 A028409 * A183559 A080553 A350432

Adjacent sequences: A348847 A348848 A348849 * A348851 A348852 A348853

Keyword

nonn,more

Author

Rémy Sigrist, Nov 01 2021

Status

approved