|
| |
|
|
A141001
|
|
a(n) = number of different landings of a grasshopper after n hops.
|
|
5
|
|
|
|
1, 1, 1, 2, 3, 4, 7, 11, 16, 21, 26, 32, 38, 44, 51, 59, 67, 75, 84, 94, 104, 114, 125, 137, 149, 161, 174, 188, 202, 216, 231, 247, 263, 279, 296, 314, 332, 350, 369, 389, 409, 429, 450, 472, 494, 516, 539, 563, 587, 611, 636, 662, 688, 714, 741, 769, 797
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Consider a grasshopper (cf. A141000) that starts at x=0 at time 0, then makes successive hops of sizes 1, 2, 3, ..., n, subject to the constraint that it must always land on a point x >= 0; sequence gives number of different places x where it can land after the n-th jump.
Here, unlike A141000, there is no restriction on how large x can be (of course x <= n(n+1)/2).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = floor(n * (n+1) / 4 - 1) for n >= 9. The induction proof for A141000 shows that for n >= 21, you hit all numbers of the right parity except n(n+1)/2-2 and n(n+1)/2-4. The floor expression handles the various parity cases. - David Applegate.
G.f.: (1 - 2*x + 2*x^2 - x^3 + x^5 + x^6 - x^7 + 2*x^8 - 2*x^9 - x^12 + x^13) / ((1 - x)^3*(1 + x^2)). - Colin Barker, May 21 2013
a(n) = (1/8+i/8) * ((-5+5*i) + (-i)^(1+n) + i^n + (1-i)*n + (1-i)*n^2) for n>8 where i=sqrt(-1).
a(n) = 3*a(n-1) - 4*a(n-2) + 4*a(n-3) - 3*a(n-4) + a(n-5) for n>9.
(End)
|
|
|
EXAMPLE
|
For example, for n=3 the grasshopper can hit 0=1+2-3 or 6=1+2+3; for n=4 it can hit 2=1+2+3-4, 4=1+2-3+4, or 10=1+2+3+4.
|
|
|
MATHEMATICA
|
LinearRecurrence[{3, -4, 4, -3, 1}, {1, 1, 1, 2, 3, 4, 7, 11, 16, 21, 26, 32, 38, 44}, 60] (* Harvey P. Dale, Mar 26 2023 *)
|
|
|
PROG
|
(PARI) Vec((1 - 2*x + 2*x^2 - x^3 + x^5 + x^6 - x^7 + 2*x^8 - 2*x^9 - x^12 + x^13) / ((1 - x)^3*(1 + x^2)) + O(x^60)) \\ Colin Barker, Aug 06 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
