A328422 Number of paths from 2 to n via maps of the form x -> x + x^j, where j is a nonnegative integer.

1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 14, 14, 18, 18, 24, 24, 31, 31, 42, 42, 51, 51, 65, 65, 79, 79, 97, 97, 118, 118, 142, 142, 167, 167, 198, 198, 229, 229, 271, 271, 317, 317, 368, 368, 419, 419, 484, 484, 549, 549, 628, 628, 707, 707, 808, 808, 905, 905, 1023

Offset

2,3

Comments

This sequence is essentially the same as the number of paths from 1 to n. However, starting from 2 removes the ambiguity of how many maps there are from 1 to 2.

a(2n+1) = a(2n) for all n because x + x^j is odd if and only if x is even and j = 0.

Links

Peter Kagey, Table of n, a(n) for n = 2..10000

Formula

a(2) = 1, a(n) = Sum_{k=1..A309978(n)} a(A328446(n,k)) for n > 2.

Example

For n = 8 the a(8) = 6 paths are:
2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 with j = [0,0,0,0,0,0]
2 -> 3 -> 4 -> 8                with j = [0,0,1]
2 -> 3 -> 6 -> 7 -> 8           with j = [0,1,0,0]
2 -> 4 -> 5 -> 6 -> 7 -> 8      with j = [1,0,0,0,0]
2 -> 4 -> 8                     with j = [1,1]
2 -> 6 -> 7 -> 8                with j = [2,0,0]

Crossrefs

Cf. A307074, A307092, A309997, A309978.

Sequence in context: A001362 A358206 A001310 * A029009 A340280 A340279

Adjacent sequences: A328419 A328420 A328421 * A328423 A328424 A328425

Keyword

nonn

Author

Peter Kagey, Oct 15 2019

Status

approved