A141002 -id:A141002 - cp's OEIS frontend

A141001 a(n) = number of different landings of a grasshopper after n hops.

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

Offset: 0

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

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).

			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.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-4,4,-3,1).

Cf. A141000, A141002.

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 *)

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

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
From Colin Barker, Aug 06 2017: (Start)
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)

A360173 Irregular triangle (an infinite binary tree) read by rows. The tree has root node 0, in row n=0. Each node then has left child m - n if nonnegative and right child m + n. Where m is the value of the parent node and n is the row of the children.

Original entry on oeis.org

0, 1, 3, 0, 6, 4, 2, 10, 9, 7, 5, 15, 3, 15, 1, 13, 11, 9, 21, 10, 8, 22, 8, 6, 20, 4, 18, 2, 16, 14, 28, 2, 18, 0, 16, 14, 30, 0, 16, 14, 12, 28, 12, 10, 26, 10, 8, 24, 6, 22, 20, 36, 11, 9, 27, 9, 7, 25, 5, 23, 21, 39, 9, 7, 25, 5, 23, 3, 21, 19, 37, 3, 21

Offset: 0

John Tyler Rascoe, Jan 28 2023

A node will have a left child only if the value of that child is greater than or equal to 0. But, each node will have a right child, since adding n will always be greater than 0.

The n-th row will have A141002(n) nodes. The leftmost border is A008344 and the rightmost is A000217.

			The binary tree starts with root 0 in row n = 0. In row n = 3, the parent node m = 3 has the first left child since 3 - 3 >= 0.
The tree begins:
row
[n]
[0]           0
               \
[1]             1
                 \
[2]            ___3___
              /       \
             /         \
[3]         0         __6__
             \       /     \
[4]           4     2      10
               \     \    /  \
[5]             9     7  5    15

Rémy Sigrist, Table of n, a(n) for n = 0..9395 (rows for n = 0..17 flattened)

Cf. A000217, A008344, A141001, A141002.

Row sums give A360229.

T:= proc(n) option remember; `if`(n=0, 0, map(x->
      [`if`(xAlois P. Heinz, Jan 30 2023

row[n_] := Module[{r = {0}}, For[h = 1, h <= n, h++, r = Flatten[If[#-h >= 0, {#-h, #+h}, {#+h}]& /@ r]]; r];
Table[row[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Apr 16 2025, after Rémy Sigrist *)

row(n) = { my (r=[0]); for (h=1, n, r=concat(apply(v->if (v-h>=0, [v-h,v+h], [v+h]), r))); return (r) } \\ Rémy Sigrist, Jan 31 2023

def A360173_rowlist(row_n):
    A = [[0]]
    for i in range(0,row_n):
        A.append([])
        for j in range(0,len(A[i])):
            x = A[i][j]
            if x - i -1 >= 0:
                A[i+1].append(x-i-1)
            if x + i + 1 >= 0:
                A[i+1].append(x+i+1)
    return(A)

A321535 Number of different ways a grasshopper can take n hops without landing on the same point more than once.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 7, 9, 14, 23, 35, 56, 86, 136, 216, 338, 535, 848, 1374, 2234, 3594, 5750, 9265, 14856, 24019, 39350, 64222, 104878, 170247, 276489, 452138, 739486, 1207429, 1974247, 3234889, 5295560, 8708262, 14276970, 23493811, 38683402, 63773042, 104840427

Offset: 0

Andrew Howroyd, Nov 12 2018

nonn

Consider a grasshopper (cf. A141000, A141002) that starts at x=0 at time 0, then makes successive hops of sizes 1, 2, 3, ..., n, subject to the constraints that it must always land on a point x >= 0 and no point may be visited more than once; sequence gives number of different ways that it can make n hops.

In other words, the number of n step self avoiding walks on a line where the n-th step has length n.

			a(6) = 4 because there are 4 walks with 6 steps:
0 -> 1 -> 3 -> 6 -> 2 -> 7 -> 13,
0 -> 1 -> 3 -> 6 -> 10 -> 5 -> 11,
0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 9,
0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 21.

Cf. A141000, A141002, A175941.

a(n)={local(f=vectorsmall(n*(n+1)/2+1)); my(recurse(p, k)=if(p>0&&!f[p], if(k==n, 1, f[p]=1; k++; my(z=self()(p+k, k) + self()(p-k, k)); f[p]=0; z))); recurse(1, 0)}

A360229 Row sums of triangle A360173.

Original entry on oeis.org

0, 1, 3, 6, 16, 36, 73, 156, 324, 677, 1405, 2864, 5906, 12058, 24548, 49928, 101434, 206173, 417141, 844256, 1707622, 3452998, 6970196, 14058528, 28368774, 57197983, 115239846, 232020596, 467296470, 940684267, 1892396396, 3805806218, 7654402454, 15391563411

Offset: 0

John Tyler Rascoe, Jan 30 2023

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..800

Cf. A141001, A141002, A360173.

b:= proc(n) option remember; `if`(n=0, 1, (p->
       add((t-> `if`(i
      add(i*coeff(p, x, i), i=0..degree(p)))(b(n))
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Jan 30 2023

b[n_] := b[n] = If[n == 0, 1, Function[p, Sum[Function[t, If[iJean-François Alcover, Apr 24 2025, after Alois P. Heinz *)

A360255 Irregular triangle (an infinite binary tree) read by rows: see Comments section for definition.

Original entry on oeis.org

0, 1, 3, 6, 2, 10, 7, 5, 15, 13, 11, 9, 21, 20, 4, 18, 2, 16, 14, 28, 12, 28, 12, 26, 8, 24, 22, 20, 36, 21, 19, 37, 21, 17, 35, 17, 33, 13, 31, 11, 29, 27, 45, 11, 31, 9, 29, 27, 47, 31, 7, 27, 25, 45, 7, 27, 23, 43, 23, 41, 19, 39, 17, 37, 35, 55, 22, 42, 18

Offset: 0

John Tyler Rascoe, Jan 30 2023

The binary tree has root node 0, in row n=0. The left child is m - n and the right child is m + n, where m is the parent node and n is the row of the child. A given node will only have a child if the child is nonnegative and the value of the child is not present in the path from the parent to the root, including the root value itself.

The n-th row will have A321535(n) nodes. The rightmost border is A000217.

			The binary tree starts with root 0 in row n = 0. In row n = 3, the parent node m = 3 does not have a left child since 3 - 3 = 0 is included in the path from the parent to the root {3,1,0}.
The tree begins:
row
[n]
[0]           0
               \
[1]             1
                 \
[2]               3
                   \
[3]               __6__
                 /     \
[4]             2      10
                 \    /  \
[5]               7  5    15

Rémy Sigrist, Table of n, a(n) for n = 0..9517 (rows for n = 0..21 flattened)

Cf. A000217, A141001, A141002, A321535, A360173.

function a = A360255( max_row )
    p = 0; a = 0; pos = 1;
    for n = 1:max_row
        for k = pos:length(a)
            h =[]; o = p(k);
            while o > 0
                h = [h a(o)]; o = p(o);
            end
            if a(k)-n > 0
                if isempty(find(h == a(k)-n, 1))
                    p = [p k]; a = [a a(k)-n];
                end
            end
            if isempty(find(h == a(k)+n, 1))
                p = [p k]; a = [a a(k)+n];
            end
        end
        pos = k+1;
    end
end % Thomas Scheuerle, Jan 31 2023

cp's OEIS Frontend

A141001 a(n) = number of different landings of a grasshopper after n hops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A360173 Irregular triangle (an infinite binary tree) read by rows. The tree has root node 0, in row n=0. Each node then has left child m - n if nonnegative and right child m + n. Where m is the value of the parent node and n is the row of the children.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

A321535 Number of different ways a grasshopper can take n hops without landing on the same point more than once.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A360229 Row sums of triangle A360173.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A360255 Irregular triangle (an infinite binary tree) read by rows: see Comments section for definition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB