A141002 a(n) = total number of different ways a grasshopper can take n hops.

1, 1, 1, 2, 3, 4, 7, 12, 21, 37, 63, 116, 208, 372, 682, 1255, 2334, 4277, 7951, 14905, 27967, 52334, 98222, 186344, 352621, 666933, 1264406, 2413511, 4604124, 8766995, 16748492, 32124034, 61642942, 118049157, 226709069, 436727197, 841581933, 1619406091

Offset: 0

Author

David Applegate and N. J. A. Sloane, Jul 21 2008

Keywords

• nonn

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 ways that it can make n hops.

Here, unlike A141000, there is no restriction on how large x can be (of course x <= n(n+1)/2).

Examples

			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. For n=7 we can reach 8 in two different ways, which explains the first place where this sequence differs from A141001.
		

Links

• David W. Wilson, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A141000, A141001.