login
A328422
Number of paths from 2 to n via maps of the form x -> x + x^j, where j is a nonnegative integer.
2
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.
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
KEYWORD
nonn
AUTHOR
Peter Kagey, Oct 15 2019
STATUS
approved