login
Triangular array read by rows: T(h,k) = number of steps from (h,k) to (0,0), where one step is (x,y) -> (x-1, y) if x is odd or (x,y) -> (y, x/2) if x is even.
5

%I #6 May 02 2015 10:14:57

%S 0,1,2,3,3,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,6,7,6,7,7,8,7,7,7,7,7,8,8,

%T 8,8,7,8,7,8,7,9,8,9,8,8,8,8,8,8,8,9,9,9,9,8,9,8,9,8,9,8,10,9,10,9,9,

%U 9,9,9,9,9,9,9,10,10,10,10,8,10,9,10,8

%N Triangular array read by rows: T(h,k) = number of steps from (h,k) to (0,0), where one step is (x,y) -> (x-1, y) if x is odd or (x,y) -> (y, x/2) if x is even.

%C The number of pairs (h,k) satisfying T(h,k) = n is F(n), where F = A000045, the Fibonacci numbers. The number of such pairs having odd h is F(n-2), and the number having even h is F(n-1).

%C Let c(n,k) be the number of pairs (h,k) satisfying T(h,k) = n; in particular, c(n,0) is the number of integers (pairs of the form (h,0)) satisfying T(h,0) = n. Let p(n) = A000931(n). Then c(n,0) = p(n+3) for n >= 0. More generally, for fixed k >=0, the sequence satisfies the recurrence r(n) = r(n-2) + r(n-3) except for initial terms.

%C The greatest h for which some (h,k) is n steps from (0,0) is H = A029744(n-1) for n >= 2, and the only such pair is (H,0).

%C T(n,k) is also the number of steps from h + k*sqrt(2) to 0, where one step is x + y*sqrt(2) -> x-1 + y*sqrt(2) if x is odd, and x + sqrt(y) -> y + (x/2)*sqrt(2) if x is even.

%H Clark Kimberling, <a href="/A257569/b257569.txt">Table of n, a(n) for n = 1..1000</a>

%e First ten rows:

%e 0

%e 1 2

%e 3 3 4

%e 4 4 5 5

%e 5 5 5 6 6

%e 6 6 6 6 7 7

%e 6 7 6 7 7 8 7

%e 7 7 7 7 8 8 8 8

%e 7 8 7 8 7 9 8 9 8

%e 8 8 8 8 8 8 9 9 9 9

%e Row 3 counts the pairs (2,0), (1,1), (0,2), for which the paths to (0,0) are as shown here:

%e (2,0) -> (0,1) -> (1,0) -> (0,0) (3 steps);

%e (1,1) -> (0,1) -> (1,0) -> (0,0) (3 steps);

%e (0,2) -> (2,0) -> (0,1) -> (1,0) -> (0,0) (4 steps).

%t f[{x_, y_}] := If[EvenQ[x], {y, x/2}, {x - 1, y}];

%t g[{x_, y_}] := Drop[FixedPointList[f, {x, y}], -1];

%t h[{x_, y_}] := -1 + Length[g[{x, y}]];

%t t = Table[h[{n - k, k}], {n, 0, 16}, {k, 0, n}];

%t TableForm[t] (* A257569 array *)

%t Flatten[t] (* A257569 sequence *)

%Y Cf. A257570, A257571, A257572, A000045, A000931, A029744.

%K nonn,tabl,easy

%O 1,3

%A _Clark Kimberling_, May 01 2015