A230871 Construct a triangle as in the Comments, read nodes from left to right starting at the root and proceeding downwards.

0, 1, 1, 3, 2, 2, 4, 8, 3, 5, 3, 5, 7, 9, 11, 21, 5, 7, 7, 13, 5, 7, 7, 13, 11, 17, 13, 23, 19, 25, 29, 55, 8, 12, 10, 18, 12, 16, 18, 34, 8, 12, 10, 18, 12, 16, 18, 34, 18, 26, 24, 44, 22, 30, 32, 60, 30, 46, 36, 64, 50, 66, 76, 144, 13, 19, 17, 31, 17, 23

Offset: 0

Author

Philippe Deléham, Nov 06 2013

Keywords

• nonn
• tabf

Comments

The rule for constructing the tree is the following:

.....x

.....|

.....y

..../ \

..y+x..3y-x

and the tree begins like this:

.........0......

.........|......

.........1......

......./ \....

......1.....3....

...../ \.../ \...

....2...2.4...8..

and so on.

Column 1 : 0, 1, 1, 2, 3, 5, 8, ... = A000045 (Fibonacci numbers).

Column 2 : 3, 2, 5, 7, 12, 19, 31, ... = A013655.

Column 3 : 4, 3, 7, 10, 17, 27, 44, ... = A022120.

Column 4 : 8, 5, 13, 18, 31, 49, 80, ... = A022138.

Column 5 : 7, 5, 12, 17, 29, 46, 75, ... = A022137.

Column 6 : 9, 7, 16, 23, 39, 62, 101, ... = A190995.

Column 7 : 11, 7, 18, 25, 43, 68, 111, ... = A206419.

Column 8 : 21, 13, 34, 47, 81, 128, 209, ... = ?

Column 9 : 11, 8, 19, 27, 46, 73, 119, ... = A206420.

The lengths of the rows are 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, ... = A011782 .

The final numbers in the rows are 0, 1, 3, 8, 21, 55, 144, ... = A001906.

The middle numbers in the rows are 1, 2, 5, 13, 34, 89, ... = A001519 .

Row sums for n>=1: 1, 4, 16, 64, 256, 1024, ... = 4^(n-1).

Examples

			The successive rows are:
  0
  1
  1, 3
  2, 2, 4, 8
  3, 5, 3, 5, 7, 9, 11, 21
  5, 7, 7, 13, 5, 7, 7, 13, 11, 17, 13, 23, 19, 25, 29, 55
  ...
		

Links

• Reinhard Zumkeller, Rows n = 0..13 of triangle, flattened

Crossrefs

Cf. A230872, A230873.

Cf. A231330, A231331, A231335.

Programs

Haskell

data Dtree = Dtree Dtree (Integer, Integer) Dtree
a230871 n k = a230871_tabf !! n !! k
a230871_row n = a230871_tabf !! n
a230871_tabf = [0] : map (map snd) (rows $ deleham (0, 1)) where
   rows (Dtree left (x, y) right) =
        [(x, y)] : zipWith (++) (rows left) (rows right)
   deleham (x, y) = Dtree
           (deleham (y, y + x)) (x, y) (deleham (y, 3 * y - x))
-- Reinhard Zumkeller, Nov 07 2013

Maple

T:= proc(n, k) T(n, k):= `if`(k=1 and n<2, n, (d->(1+2*d)*
      T(n-1, r)+(1-2*d)*T(n-2, iquo(r+1, 2)))(irem(k+1, 2, 'r')))
    end:
seq(seq(T(n, k), k=1..max(1, 2^(n-1))), n=0..7); # Alois P. Heinz, Nov 07 2013

Mathematica

T[n_, k_] := T[n, k] = If[k==1 && n<2, n, Function[d, r = Quotient[k+1, 2]; (1+2d) T[n-1, r] + (1-2d) T[n-2, Quotient[r+1, 2]]][Mod[k+1, 2]]];
Table[T[n, k], {n, 0, 7}, {k, 1, Max[1, 2^(n-1)]}] // Flatten (* Jean-François Alcover, Apr 11 2017, after Alois P. Heinz *)

Extensions

Incorrect formula removed by Michel Marcus, Sep 23 2023